C++でサイズnのソート済み配列から唯一の重複要素を見つける方法

問題概要

この問題では、1からN-1までの値が格納されたサイズNの配列arr[]が与えられます。ただし、そのうち1つの値だけが2回出現しています。私たちのタスクは、サイズnのソート済み配列の中で唯一繰り返されている要素を見つけることです。

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

入力：

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

出力：

5

解法アプローチ1：線形探索（O(N)）

最もシンプルな解き方は、線形探索を用いる方法です。配列を先頭から順に走査しながら、隣接する要素arr[i]とarr[i+1]の値を比較します。両者が一致した場合、その値が重複している要素となるため、arr[i]を返します。

この方法の時間計算量はO(N)であり、実装も非常に簡単ですが、大規模な配列に対しては非効率になる可能性があります。

サンプルコード

#include <iostream>
using namespace std;
int findRepeatingValueArr(int arr[], int N){
    for(int i = 0; i < N; i++){
        if(arr[i] == arr[i+1])
            return (arr[i]);
    }
    return -1;
}
int main(){
    int arr[] = {1, 2, 3, 4, 4, 5, 6};
    int N = sizeof(arr)/sizeof(arr[0]);
    cout<<"配列内の重複している値は "<<findRepeatingValueArr(arr, N);
    return 0;
}

出力：

配列内の重複している値は 4

解法アプローチ2：二分探索（O(log N)）

より効率的なアプローチとして、二分探索アルゴリズムを活用する方法があります。この問題の重要な性質として、配列には1からN-1までの値が含まれているため、重複が存在しない場合、インデックスiの位置にある値は必ず「i + 1」と一致します。

この性質を利用すると、以下のように判断できます。

• 中央インデックスmidにおいてarr[mid] == mid + 1の場合 → 重複は右側の部分配列に存在する
• arr[mid] != mid + 1の場合 → 重複は左側の部分配列に存在する
• さらにarr[mid] == arr[mid-1]が成り立つ場合 → arr[mid]が求める重複要素

探索範囲を半分ずつ絞り込んでいくことで、時間計算量O(log N)で効率的に答えを求められます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int findRepeatingValueArr(int arr[], int s, int e){
    if (s > e)
        return -1;
    int mid = (s + e) / 2;
    if (arr[mid] != mid + 1){
        if (mid > 0 && arr[mid]==arr[mid-1])
            return arr[mid];
        return arr[findRepeatingValueArr(arr, s, mid-1)];
    }
    return arr[findRepeatingValueArr(arr, mid+1, e)];
}
int main(){
    int arr[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"配列内の重複している値は "<<findRepeatingValueArr(arr, 0, n-1);
    return 0;
}

出力：

配列内の重複している値は 6

まとめ

ソート済み配列から唯一の重複要素を見つける問題では、単純な線形探索でも解けますが、配列の値とインデックスの対応関係を利用した二分探索を使うことで、計算量をO(N)からO(log N)へ大幅に改善できます。データ量が多い場合は、二分探索によるアプローチが特に有効です。