C++で1からn-1の範囲に存在する唯一の重複要素を見つける方法

問題概要

この問題では、サイズNの順序が整列されていない整数配列 arr[] が与えられます。配列には 1 から N-1 までの値がすべて含まれており、そのうちの1つの値だけが2回出現しています。このとき、1からn-1までの範囲に存在する唯一の重複要素を見つけるのが課題です。

具体例で問題を確認しましょう。

入力：

arr[] = {3, 5, 4, 1, 2, 1}

出力：

1

この例では、配列内で「1」のみが2回出現しているため、答えは 1 となります。

解法1：全探索（ブルートフォース）

最もシンプルな解決策は、配列を走査しながら、各要素について配列内の他の位置に同じ値が存在するかどうかを調べることです。同じ値が見つかった時点で、その値を結果として返します。

この手法は二重ループを使用するため、計算量は O(N²) となります。理解しやすい反面、配列サイズが大きくなると処理が遅くなる点に注意が必要です。

サンプルコード

#include <iostream>
using namespace std;
int findRepValArr(int arr[], int n){
   for(int i = 0; i < n; i++)
   for(int j = i+1; j < n; j++)
   if(arr[i] == arr[j])
      return arr[i];
}
int main(){
   int arr[] = { 5, 3, 2, 6, 6, 1, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The repetitive value in the array is "<<findRepValArr(arr, n);
   return 0;
}

実行結果

The repetitive value in the array is 6

解法2：数学的アプローチ（総和の差を利用）

より効率的な解法として、数学的な性質を利用する方法があります。配列には 1 から N-1 までの値がそれぞれ1回ずつ含まれ、1つの値だけが余分に出現しています。そこで、「配列全体の合計」から「1から N-1 までの自然数の合計」を引けば、その差がすなわち重複要素となります。

1 から N-1 までの自然数の和（S_n）は、次の公式で求められます。

S_n = n × (n−1) / 2

重複要素（doubleVal）は以下のように計算できます。

doubleVal = arrSum − S_n

この手法は配列を一度走査するだけで済むため、時間計算量は O(N)、追加のメモリも不要であり、解法1よりも大幅に効率的です。

サンプルコード

#include <iostream>
using namespace std;
int findRepValArr(int arr[], int n){
   int arrSum = 0;
   for(int i = 0; i < n; i++)
      arrSum += arr[i];
   int sn = (((n)*(n-1))/2);
   return arrSum - sn;
}
int main(){
   int arr[] = { 5, 3, 2, 6, 6, 1, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The repetitive value in the array is "<<findRepValArr(arr, n);
   return 0;
}

実行結果

The repetitive value in the array is 6

まとめ

重複要素の検索には、全探索による O(N²) の方法と、総和の差を利用した O(N) の方法があります。どちらも正しく動作しますが、実用上は計算量の少ない数学的アプローチを採用するのがおすすめです。データの制約条件によって最適な手法を選択しましょう。