C++で指定された制約条件下で重複要素を検索する方法

問題の概要

6種類の異なる数値からなるリストがあり、そのうち1つの数値だけが5回繰り返し出現しています。つまり、配列には合計10個の要素が存在することになります。この重複している数値を、たった2回の比較だけで見つけ出すのが本記事の課題です。

例えば、リストが [1, 2, 3, 4, 4, 4, 4, 4, 5, 6] の場合、重複している数値は 4 なので、出力は「4」となります。

アルゴリズムの考え方

ここでは、配列が昇順にソートされているものとします。合計10個の要素の中に同じ数値が5個連続して並んでいる場合、そのブロックは必ずインデックス3から5の範囲のいずれかに位置します。これは、5個の連続した同一要素を10個のスロットのどこに配置しても、中央付近であるインデックス3・4・5の少なくとも1つと必ず重なるためです。

したがって、array[3] と array[4]、さらに array[4] と array[5] の値を比較するだけで重複要素を特定できます。どちらの比較でも等しくならない場合は、重複ブロックが後半に寄っていることを意味するため、array[5] が答えになります。

C++での実装例

#include<iostream>
using namespace std;
int getDuplicate(int array[]) {
    if (array[3] == array[4])
        return array[3];
    else if (array[4] == array[5])
        return array[4];
    else
        return array[5];
}
int main() {
    int a[] = {1, 2, 3, 4, 4, 4, 4, 4, 5, 6};
    cout << "Duplicate element: " << getDuplicate(a);
}

実行結果

Duplicate element: 4

まとめ

この手法を使えば、全要素を順番に走査することなく、わずか2回の比較で重複要素を特定できます。計算量はO(1)であり、「比較回数を最小限に抑えたい」という制約条件下で非常に有効なアプローチです。ただし、前提として配列がソート済みである点に注意が必要です。