ホームページ  >  記事  >  バックエンド開発  >  C++ を使用して配列内の一意のペアの数を見つける

C++ を使用して配列内の一意のペアの数を見つける

WBOY
WBOY転載
2023-09-07 11:53:09522ブラウズ

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

解決策を見つける方法

この問題を解決するには 2 つの方法があります。それらは -

ブルート フォース メソッド

この方法では、考えられる各ペアをループし、これらのペアをセットに追加し、最後にセットのサイズを見つけます。この方法の時間計算量は O(n2 log n) です。

#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;
}

出力

Number of unique pairs : 16

上記のコードの説明

このコードでは、最初にコレクション変数を宣言し、次にすべてのループを 2 つ使用します。可能な要素のペアを選択し、i と j を使用して各ペアをセットに挿入します。次に、コレクションのサイズを計算し、結果を出力します。

効率的な方法

もう 1 つの方法は、まず配列内の一意の数値の数を見つけることです。これで、他のすべての一意の要素は、それ自体の 1 つのペアを除く他の一意の要素で作成できるようになります。一意のペアの数は、すべての一意の数値の 2 乗に等しくなります。このメソッドの時間計算量は O(n) です。

#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;
}

出力

Number of unique pairs : 16

上記のコードの説明

このコードでは、コレクションを宣言し、配列の各要素を反復処理します。要素を追加し、各要素をコレクションに挿入します。その後、セットのサイズを計算し、式 n2 に従って結果を求め、出力を出力しました。

結論

この記事では、配列内で一意のペアを見つける問題を解決し、シンプルと効率の 2 つの解決策について説明しました。単純なアプローチでは、考えられるすべてのペアを O(n2 log n) の時間計算量でセットに挿入しますが、効率的なアプローチでは、すべての一意の数値を見つけて、結果を n2 で求めます。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用して配列内の一意のペアの数を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事はtutorialspoint.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。