C++를 사용하여 배열의 고유 쌍 수 찾기-C++-php.cn

C++를 사용하여 배열의 고유 쌍 수 찾기

WBOY

풀어 주다： 2023-09-07 11:53:09

앞으로

554명이 탐색했습니다.

C++를 사용하여 배열의 고유 쌍 수 찾기

C++의 배열 구문에서 여러 개의 고유한 쌍을 생성하려면 적절한 지식이 필요합니다. 고유 쌍의 수를 찾는 동안 주어진 배열의 모든 고유 쌍을 계산합니다. 즉, 각 쌍이 고유해야 하는 모든 가능한 쌍이 형성될 수 있습니다. 예를 들어 -

Input : array[ ] = { 5, 5, 9 }
Output : 4
Explanation : The number of all unique pairs are (5, 5), (5, 9), (9, 5) and (9, 9).

Input : array[ ] = { 5, 4, 3, 2, 2 }
Output : 16

로그인 후 복사

해결 방법을 찾는 방법

이 문제를 해결하는 방법에는 두 가지가 있습니다. 그들은 −

무차별 대입 방법

이 방법에서는 이러한 쌍을 컬렉션에 추가하여 가능한 모든 쌍을 반복합니다. 컬렉션의 크기를 찾으십시오. 이 방법의 시간 복잡도는 O(n2 log n)입니다.

Example

#include <bits/stdc++.h>
using namespace std;
int main () {
   int arr[] = { 5, 4, 3, 2, 2 };
   int n = sizeof (arr) / sizeof (arr[0]);
   // declaring set to store pairs.
   set < pair < int, int >>set_of_pairs;

   for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
         set_of_pairs.insert (make_pair (arr[i], arr[j]));

   int result = set_of_pairs.size();

   cout <<"Number of unique pairs : " << result;
   return 0;
}

로그인 후 복사

Output

Number of unique pairs : 16

로그인 후 복사

위 코드 설명

이 코드에서는 먼저 집합 변수를 선언한 다음 두 개의 루프를 사용하여 가능한 모든 요소 쌍을 반복하고 i 및 j를 사용하여 각 쌍을 변환합니다. 요소는 다음과 같습니다. 컬렉션에 삽입되었습니다. 그런 다음 컬렉션의 크기를 계산하고 결과를 인쇄합니다.

효율적인 방법

또 다른 방법은 먼저 배열의 고유 숫자 수를 알아내는 것입니다. 이제 그 자체를 제외하고 다른 모든 고유 요소는 다른 고유 요소와 쌍을 만들 수 있으므로 고유 쌍 수는 다음과 같습니다. 모든 고유수의 제곱. 이 방법의 시간 복잡도는 O(n)입니다.

Example

#include <bits/stdc++.h>
using namespace std;

int main () {
   int arr[] = { 5, 4, 3, 2, 2 };
   int n = sizeof (arr) / sizeof (arr[0]);

   // declaring set to store unique elements.

   unordered_set < int >set_of_elements;
   // inserting elements in the set.
   for (int i = 0; i < n; i++)
      set_of_elements.insert (arr[i]);

   int size = set_of_elements.size ();
   // finding number of unique pairs
   int result = size * size;

   cout << "Number of unique pairs in an array: " << result;
   return 0;
}

로그인 후 복사

Output

Number of unique pairs : 16

로그인 후 복사

위 코드 설명

이 코드에서는 컬렉션을 선언한 다음 배열의 각 요소를 반복하고 각 요소를 컬렉션에 삽입합니다. 그런 다음 세트의 크기를 계산하고 n2 공식에 따라 결과를 찾아 출력을 인쇄했습니다.

결론

이 기사에서는 배열에서 고유한 로그 쌍을 찾는 문제를 해결하고 간단하고 효율적인 두 가지 솔루션에 대해 논의했습니다. 간단한 접근 방식에서는 가능한 모든 쌍을 O(n2 log n) 시간 복잡도로 집합에 삽입하는 반면, 효율적인 접근 방식에서는 모든 고유 숫자를 찾고 n2로 결과를 찾습니다. C, Java, Python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 C++를 사용하여 배열의 고유 쌍 수 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!