C++で配列内に存在しない数値をすべて検索する方法

n個の要素からなる配列を考えてみましょう。いくつかの要素は2回現れ、それ以外は1回だけ現れます。各要素は 1 ≤ A[i] ≤ n の範囲に収まっています。このとき、配列の中に存在しない数値をすべて見つけ出す必要があります。ただし制約として、追加のメモリ領域を使用せず、計算時間は O(n) 以内で解かなければなりません。

たとえば、配列が [4, 3, 2, 7, 8, 2, 3, 1] である場合、答えは [5, 6] になります。

解法のアプローチ

この問題は「符号反転によるマーキング」というテクニックを使うことで、追加メモリなしで解決できます。手順は以下の通りです。

• n を配列のサイズとする
• i を 0 から n − 1 まで繰り返す
  • x := |A[i]| − 1
  • A[x] > 0 であれば、A[x] := −A[x] とする
• 答えを格納する配列を用意する
• i を 0 から n − 1 まで繰り返す
  • A[i] > 0 であれば、i + 1 を答えの配列に追加する
• 答えの配列を返す

仕組みのポイント

このアルゴリズムでは、値 v が配列内に出現したら、インデックス v−1 の位置にある要素を負の値に書き換えて「出現済み」の印をつけます。すべての走査が終わった後も正の値のまま残っているインデックス i は、「数値 i + 1 が一度も現れなかった」ことを意味します。これにより、ハッシュセットなどの追加データ構造を使わずに、欠損している数値だけを効率的に特定できます。

実装例

理解を深めるために、以下のC++実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]";
}
class Solution {
    public:
    vector<int> findDisappearedNumbers(vector<int>& v) {
        int n = v.size();
        for(int i = 0;i < n; i++){
            int x = abs(v[i]) - 1;
            if(v[x] > 0) v[x] = -v[x];
        }
        vector <int> ans;
        for(int i = 0; i < n; i++){
            if(v[i]>0)ans.push_back(i+1);
        }
        return ans;
    }
};
main(){
    Solution ob;
    vector<int> v{4,3,2,7,8,2,3,5};
    print_vector(ob.findDisappearedNumbers(v));
}

入力

[4,3,2,7,8,2,3,5]

出力

[1, 6]