C++で配列内の等しい要素を持つインデックスペアを数える方法

N個の要素からなる配列が与えられたとき、「同じ値を持ち、かつインデックスが異なる」ペア (i, j) の数を求めるのが本記事の目的です。つまり、Arr[i] == Arr[j] かつ i ≠ j を満たす組み合わせを数えます。

これは現実の問題にも応用できます。たとえば、N個の手袋の中から同じサイズの手袋同士でペアを作る場面を考えてみましょう。売れるのはペアになった手袋だけであり、片方だけでは価値がありません。そこで、一致する要素を見つけてはペアとして取り除いていく処理が必要になります。

基本的な考え方

二重ループを用いて、外側のループを 0 ≤ i < n−1、内側のループを i < j < n の範囲で回します。各ペア (i, j) について、次の条件を満たすかどうかを判定します。

• Arr[i] == Arr[j](値が等しい)
• Arr[i] > 0 かつ Arr[j] > 0(まだ未使用である)

条件を満たしたらペア数をカウントアップし、該当する2つの要素を -1 に書き換えて以降のチェック対象から除外します。手袋のサイズが -1 になることはないため、これで「使用済み」を表現できるのです。

具体例で理解する

例1

入力: Arr[] = { 4, 3, 2, 1, 2, 4 }、N = 6

出力: 等しい要素を持つインデックスペアの数 = 2

count=0, Arr[]= [ 4,3,2,1,2,4 ]
Arr[0]=Arr[5], 0!=5, count=1 → Arr[0]=Arr[5]=-1 → [ -1,3,2,1,2,-1 ]
Arr[2]=Arr[4], 2!=4, count=2 → Arr[2]=Arr[4]=-1 → [ -1,3,-1,1,-1,-1 ]
これ以上、値が等しく i!=j かつ -1 より大きいペアは存在しない。合計ペア数=2

例2

入力: Arr[] = { 2, 2, 2, 2, 2 }、N = 5

出力: 等しい要素を持つインデックスペアの数 = 2

count=0, Arr[]= [ 2,2,2,2,2 ]
Arr[0]=Arr[1], 0!=1, count=1 → Arr[0]=Arr[1]=-1 → [ -1,-1,2,2,2 ]
Arr[2]=Arr[3], 2!=3, count=2 → Arr[2]=Arr[3]=-1 → [ -1,-1,-1,-1,2 ]
残りの要素1個ではペアが作れないため、合計ペア数=2

アルゴリズムの手順

• 手袋のサイズ(> 0)を表す正の整数で初期化された配列 Arr[] を用意します。
• 配列の長さを格納する変数 n を定義します。
• 関数 countPairs(int arr[], int n) は、配列とその長さを受け取り、値が等しくインデックスが異なるペアの総数を返します。
• 外側のループを 0 ≤ i < n−1、内側のループを i < j < n で走査します。
• arr[i] と arr[j] がともに正であり、かつ arr[i] == arr[j] ならば count を増やします(ループ構造上、i == j になることはないため比較は不要です)。
• マッチした要素を arr[i] = arr[j] = -1 として、再びカウントされないようにします。
• すべてのループが終わった時点の count が、完成した手袋のペア総数となります。
• count を結果として返します。

C++での実装例

// 上記アプローチのC++実装
#include <bits/stdc++.h>
using namespace std;

// 等しい要素を数えて手袋のペアを作る関数
int countPairs(int arr[], int n){
    int count = 0;
    for(int i=0; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            if(arr[i]==arr[j] && arr[i]>0 && arr[j]>0){
                count++;
                arr[i]=arr[j]=-1; // 使用済みとしてマーク
            }
        }
    }
    return count;
}

int main(){
    int arr[] = { 1,2,4,2,1,2,4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Pair of gloves ( Equal element pairs ):" << countPairs(arr, n);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

Pair of gloves ( Equal element pairs ):3.

この例では {1, 1}、{2, 2}、{4, 4} の3組のペアが成立し、余った 2 はペアになれないため、答えは 3 となります。

計算量について

この手法は二重ループを使用するため、時間計算量は O(n²) です。配列のサイズが小〜中規模であれば十分実用的ですが、要素数が非常に多い場合は、ハッシュマップ(unordered_map)で各値の出現回数を数え、回数 ÷ 2 の合計を求めることで O(n) に改善できます。