C++で配列内の重複要素を検出する方法：O(n)時間・O(1)の追加メモリを実現する符号マーキング技法

はじめに

0からn-1までの範囲の数値が格納された配列を考えます。このとき、同じ数値が複数回出現することがあります。追加のメモリ領域を使わずに、これらの重複している数値をすべて見つけるのが本記事の目的です。

例えば、n = 7 の場合で配列が [5, 2, 3, 5, 1, 6, 2, 3, 4, 5] のとき、答えは 5, 2, 3 となります。

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

この問題を解く鍵となるのは「符号マーキング（sign marking）」というテクニックです。配列の各値が必ず 0 ～ n-1 の範囲に収まっているため、その値自体を配列のインデックスとして利用できます。具体的には、以下の手順に従います。

• 配列内の各要素 e について、次の処理を行います。
  • e の絶対値をインデックスとして、A[|e|] の符号を確認します。
  • 符号が正であれば、その要素を負の値に書き換えます（「この値は既に登場した」という目印になります）。
  • すでに負になっている場合は、その値は重複していることを意味します。

この方法なら、ハッシュセットなどの追加データ構造を一切使わずに、元の配列自身を目印として活用できるため、時間計算量 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

コードの解説

findDuplicates 関数では、配列を先頭から順に走査します。各要素について abs(arr[i]) で絶対値を取り、それをインデックスとして該当位置の値が正かどうかを判定します。

• 正の場合：まだ一度も訪れていない値なので、その位置の値を負に反転させて「訪問済み」の印を付けます。
• 負の場合：既に同じ値が出現しているため、abs(arr[i]) を出力して重複として報告します。

上記のサンプルコードでは、入力配列 {5, 2, 3, 5, 1, 6, 2, 3, 4, 1} に対して、重複値である 5, 2, 3, 1 が出力されます。

注意点

この手法は「配列の値が 0 以上 n-1 以下の整数である」という前提条件が必要です。また、元の配列の符号情報が失われるため、処理後に元の配列を復元したい場合は、再度絶対値を取って戻す必要があります。負の値や範囲外の値が含まれる配列には適用できない点にも留意してください。