O(n)時間・O(1)の追加メモリで重複要素を検出する方法 - C++実装（その1）

0からn-1までの範囲の数値が格納されたリストがあるとします。同じ数値は何度でも繰り返し出現する可能性があります。ここで求めたいのは、追加のメモリを使用せずに、繰り返し現れる数値をすべて検出することです。

例として、リストが [5, 2, 3, 5, 1, 6, 2, 3, 4, 1] の場合を考えてみましょう。このとき答えは 5, 2, 3, 1 となります。

解法のアプローチ

この問題を解くには、リスト内の各要素 e に対して、以下の手順を実行します。

• sign := A[e の絶対値] を確認する
• sign が正の値であれば、その値を負に変更する
• すでに負の値であれば、その数値は重複していると判断する

アルゴリズムのポイント

この手法の鍵となるのは、配列のインデックスと符号をうまく活用する点です。要素の値をそのままインデックスとして扱い、対応する位置の値の符号を「出現済み」のフラグとして利用します。値がまだ正のままなら初回の出現、すでに負になっていれば2回目以降の出現、つまり重複であると判断できます。これにより、ハッシュセットなどの追加データ構造を用意することなく、O(n)時間・O(1)の追加メモリで重複検出が可能になります。

サンプルコード（C++）

#include<iostream>
#include<cmath>
using namespace std;
void findDuplicates(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        if (arr[abs(arr[i])] >= 0)
            arr[abs(arr[i])] *= -1;
        else
            cout << abs(arr[i]) << " ";
    }
}
int main() {
    int arr[] = {5, 2, 3, 5, 1, 6, 2, 3, 4, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    findDuplicates(arr, n);
}

出力結果

5 2 3 1

注意点

このアルゴリズムには、処理の過程で配列の元の値の符号が変更される（元の配列が破壊される）という副作用があります。元の配列を保持する必要がある場合は、処理後に各要素の絶対値を取って復元するか、別の手法を検討しましょう。また、この手法が正しく動作するためには、配列内のすべての要素が 0 以上 n 未満の範囲に収まっていることが前提条件となります。