C++에서 정렬된 배열의 절대 고유 개수?

배열은 동일한 데이터 유형의 요소 모음입니다. 정렬된 배열 오름차순 또는 내림차순으로 저장된 요소가 있는 배열입니다.

고유 개수는 동일하지 않은 요소의 수입니다.

절대 고유 개수는 요소, 즉 부호가 없는 요소(부호 없는 값)의 절대값에 대한 고유 개수입니다.

이 프로그램에서 우리는 정렬된 배열에서 절대 고유 개수를 찾을 것입니다. 즉, 배열의 각 요소의 절대값을 고려하면 고유한 값의 수를 계산합니다.

예를 들어,

Input : [-3 , 0 , 3 , 6 ]
Output : 3

배열에는 3개의 고유한 절대값이 있으며 요소는 0, 3, 6입니다.

이 문제를 해결하기 위해 다양한 방법을 사용하는 방법이 있습니다.

세트를 사용하여

집합에는 항상 고유한 요소가 포함됩니다. 따라서 집합의 절대값을 확인하고 사용할 수 없는 경우 언제 요소를 집합에 추가할지 확인합니다. 세트의 크기를 반환합니다.

알고리즘 −

• 배열과 동일한 데이터 유형의 집합을 만듭니다.

• 각 요소의 절대값을 찾아 배열에 저장합니다. 집합은 여러 값을 만나더라도 하나의 단일 값을 저장합니다.

• 모든 요소를 ​​입력한 후. 집합의 길이를 반환합니다. 이렇게 하면 고유한 요소의 수가 배열로 표시됩니다.

예시

#include <bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = {-3, 0, 2, 6};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Count of absolute distinct values : ";
   unordered_set<int> s;
   for (int i = 0 ; i < n; i++)
      s.insert(abs(arr[i]));
      int nof = s.size();
      cout<<nof;
      return 0;
}

출력

Count of absolute distinct values : 4

배열 검사 및 카운트 변수 사용

이 방법은 집합 대신 단일 변수만 사용합니다. 배열의 고유한 요소를 계산하는 count 변수를 제공합니다.

예시

#include <iostream>
using namespace std;
int main() {
   int arr[] = {-5, -1, 0, 5, 8};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Count of absolute distinct values : ";
   int count = n;
   int i = 0, j = n - 1, sum = 0;
   while (i < j) {
      while (i != j && arr[i] == arr[i + 1])
         count--, i++;
      while (i != j && arr[j] == arr[j - 1])
         count--, j--;
      if (i == j)
         break;
      sum = arr[i] + arr[j];
      if (sum == 0) {
         count--;
         i++, j--;
      }
      else if(sum < 0)
         i++;
      else
         j--;
   }
   cout<< count;
   return 0;
}

출력

Count of absolute distinct values : 4