C++でセットの不一致問題を解く：重複した数と欠落した数を見つける方法

1からnまでの数字を含む集合Sがあるとします。ところが、何らかのエラーによって、集合内のある数字が別の数字の位置に誤って記録されてしまい、その結果、ある一つの数字が重複し、別の一つの数字が失われるという状態になりました。

ここで、エラー発生後の集合の状態を表す配列numsが与えられます。私たちのタスクは、2回出現している数字と失われた数字を見つけ出し、その結果を配列として返すことです。

例えば、入力が [1,2,3,4,4,6] の場合、4が重複しており5が欠落しているため、出力は [4,5] となります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• サイズ2の結果格納用配列 v を定義します
• s1 := 配列Aの全要素の合計
• n := 配列Aのサイズ
• exp_sum := n × (n + 1) ÷ 2（1からnまでの期待される合計）
• i を 0 から n 未満まで1ずつ増やしながらループ処理を行います
  • A[|A[i]| − 1] > 0 の場合：A[|A[i]| − 1] = −A[|A[i]| − 1] として該当要素を負の値にします
  • それ以外の場合（すでに負になっている＝重複を検出）：v[0] := |A[i]| とし、ループを抜けます
• v[1] := v[0] − (s1 − exp_sum)
• v を返します

アルゴリズムの仕組み

このアルゴリズムは「符号マーキング」というテクニックを活用しています。各要素の値をインデックスとして利用し、対応する位置の要素を負の値に書き換えることで、「その数字は既に出現済みである」という印をつけていきます。アクセスしようとした位置がすでに負になっていた場合、その値が重複していることが確定します。

さらに、実際の合計 s1 と期待される合計 exp_sum の差分から、欠落した数字を導き出せます。重複した数を d、欠落数を m とすると、s1 − exp_sum = d − m という関係が成り立つため、m = d − (s1 − exp_sum) として求められます。この方法なら追加のメモリをほとんど使わずに効率よく解けます。

実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    vector<int> findErrorNums(vector<int>& A) {
        vector<int> v(2);
        long long int s1 = accumulate(A.begin(), A.end(), 0);
        int n = A.size();
        long long int exp_sum = (n * (n + 1)) / 2;
        for (int i = 0; i < n; i++) {
            if (A[abs(A[i]) - 1] > 0) {
                A[abs(A[i]) - 1] = -A[abs(A[i]) - 1];
            }
            else {
                v[0] = abs(A[i]);
                break;
            }
        }
        v[1] = v[0] - (s1 - exp_sum);
        return v;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,4,4,6};
    print_vector(ob.findErrorNums(v));
}

入力

{1,2,3,4,4,6}

出力

[4, 5]

このように、入力配列に対して一度の走査で重複した数（4）と欠落した数（5）を正しく検出できていることが確認できます。時間計算量はO(n)、追加の領域計算量はO(1)（出力用配列を除く）であり、非常に効率的な解法と言えます。