정렬된 배열의 절대 고유 개수?

이 섹션에서는 절대값이 서로 다른 요소의 수를 계산하는 방법을 살펴보겠습니다. 배열에 {5, 5, 6, -5, 8, 2, -2, 1}과 같은 요소가 거의 없다고 가정하여 8개의 요소가 있습니다. 그러나 구별되는 5개의 요소 {5, 6, 8, 2, 1}가 있습니다. -5와 5는 다른 것으로 간주되지 않고 절대값이 동일하므로 동일합니다.

이 문제를 해결하기 위해 Set 데이터 구조를 사용할 것입니다. 세트에서 중복 요소는 허용되지 않습니다. 그리고 집합에 항목을 삽입할 때 절대값만 푸시합니다.

알고리즘

absoluteDistinctCount(arr)

begin
   define set s;
   for each element e in arr, do
      insert |e| into s
   done
   return the number of elements of s
end

예시

#include<iostream>
#include<set>
#include<cmath>
using namespace std;
int absoluteDistinctCount(int arr[], int n){
   set<int> s;
   for(int i = 0; i<n; i++){
      s.insert(abs(arr[i])); //insert the absolute value
   }
   return s.size();
}
main() {
   int arr[] = {5, 5, 6, -5, 8, 2, -2, 1};
   int n = (sizeof(arr))/(sizeof(arr[0]));
   cout << "Absolute Distinct Count: " << absoluteDistinctCount(arr, n);
}

출력

Absolute Distinct Count: 5