C++でO(1)の追加メモリを使って配列内の重複要素を効率的に検出する方法

問題の概要

0からn-1までの範囲の数値が格納された配列を考えます。このとき、同じ数値は何度でも繰り返し現れる可能性があります。ここでの課題は、余分なメモリ（補助配列など）を使用せずに、重複している数値をすべて見つけることです。

例えば、n = 7 の場合で、配列が [5, 2, 3, 5, 1, 6, 2, 3, 4, 5] のようになっているとします。このとき答えは 5, 2, 3 となります。

アルゴリズムの考え方：符号マーキング法

この問題をO(1)の追加空間で解く鍵となるのが「符号（正負）をマーキングとして利用する」テクニックです。配列の要素はすべて0からn-1の範囲内であるため、各値は必ず配列内の有効なインデックスに対応します。この性質を利用して、配列そのものを訪問済みフラグとして活用します。

具体的な手順は以下の通りです。

• 配列内の各要素 e に対して、以下の処理を行います。
  • sign := A[|e|]（要素eの絶対値をインデックスとして、その位置の符号を確認）
  • その値が正であれば、負の値に書き換える（＝この値は初めて出現したことを記録）
  • すでに負であれば、その値は以前にも出現しているため重複であると判定し、出力する

この方法では、配列の要素を一時的に負の値に変更しますが、新しい配列やハッシュマップなどの追加データ構造を一切必要としないため、空間計算量はO(1)となります。時間計算量は配列を一度だけ走査するためO(n)です。

なお、元の配列の値が変更されてしまう点に注意が必要です。元の配列を復元したい場合は、処理後に再度絶対値を取って戻すことで対応できます。

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);
    return 0;
}

実行結果

5 2 3 1

コードの解説

findDuplicates 関数では、配列の各要素について abs(arr[i]) をインデックスとして扱い、その位置の値の符号を確認しています。

• 値が0以上（正）の場合：その値は初めての登場なので、*= -1 で負にマーキングします。
• 値が負の場合：すでに同じ値が出現済みであることを意味するため、その絶対値を出力します。

上記の実行例では、配列 {5, 2, 3, 5, 1, 6, 2, 3, 4, 1} の中で重複している 5, 2, 3, 1 が順に出力されます。

計算量

• 時間計算量： O(n) — 配列を一度だけ走査します。
• 空間計算量： O(1) — 補助的なデータ構造を使用せず、入力配列自体をフラグとして利用します。

まとめ

要素が0からn-1の範囲に収まる配列の重複検出は、符号マーキングのテクニックを使うことで、追加メモリなしで効率的に解決できます。配列の値が書き換わることを許容できる場面では、非常にシンプルかつ実用的なアプローチです。