C++で配列内の一意なペア（ユニークペア）の数を求める方法をわかりやすく解説

C++で配列内に存在する一意なペア（ユニークペア）の数を求めるには、適切な考え方と実装方法を理解しておく必要があります。一意なペアの数を数えるとは、与えられた配列から作成できるすべてのペアの中で、重複しないペアだけをカウントすることを意味します。例えば、次のようなケースが挙げられます。

入力 : array[ ] = { 5, 5, 9 }
出力 : 4
説明 : 一意なペアは (5, 5)、(5, 9)、(9, 5)、(9, 9) の4つです。

入力 : array[ ] = { 5, 4, 3, 2, 2 }
出力 : 16

解決のためのアプローチ

この問題を解くには、主に2つのアプローチがあります。

1. 全探索（ブルートフォース）アプローチ

この方法では、考えられるすべてのペアを走査してセット（set）に格納し、最後にセットのサイズを取得することで答えを求めます。すべてのペアを生成するためシンプルで分かりやすい反面、計算量は O(n² 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]);
    // ペアを格納するためのセットを宣言
    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

コードの解説

このコードでは、まずペアを格納するためのセット変数を宣言します。次に、二重ループを使ってインデックス i と j により考えられるすべてのペアを走査し、それぞれのペアをセットに挿入していきます。セットは重複する要素を自動的に排除してくれるため、最後にセットのサイズを取得すれば、それがそのまま一意なペアの総数になります。

2. 効率的なアプローチ

もう一つの方法は、まず配列内の一意な要素（重複しない値）の数を求めることです。各一意な要素は、自分自身を含む他のすべての一意な要素とペアを作ることができるため、一意なペアの総数は「一意な要素数の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]);

    // 一意な要素を格納するセットを宣言
    unordered_set < int >set_of_elements;
    // 配列の要素をセットに挿入
    for (int i = 0; i < n; i++)
        set_of_elements.insert (arr[i]);

    int size = set_of_elements.size ();
    // 一意なペアの数を求める
    int result = size * size;

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

出力

Number of unique pairs : 16

コードの解説

このコードでは、まずセットを宣言し、配列の各要素を順番にセットへ挿入していきます。unordered_set は重複する要素を自動的に取り除くため、セットには一意な値のみが残ります。その後、セットのサイズを取得し、「サイズ × サイズ（n²）」という式から一意なペアの総数を計算して結果を出力しています。

まとめ

本記事では、配列内の一意なペアの数を求める問題について、シンプルな方法と効率的な方法の2つの解き方を解説しました。シンプルな全探索では、すべてのペアをセットに挿入するため計算量は O(n² log n) になりますが、効率的な方法では一意な要素数を求めて2乗するだけで O(n) で答えを得られます。なお、同じプログラムはC言語、Java、Pythonなど他のプログラミング言語でも同様の考え方で実装できます。この記事が皆さんの学習に役立てば幸いです。