Pythonで1〜Nの範囲の配列から欠落している4つの数を検索する方法

問題の概要

ここでは、1からNまでの範囲に属する相異なる整数で構成された配列を扱います。配列のサイズは N-4 であり、要素の重複は一切ありません。つまり、1からNまでのうち4つの数が配列から抜け落ちていることになります。この記事では、その4つの欠落数を昇順で特定する方法を解説します。

例として、入力が A = [2, 8, 4, 13, 6, 11, 9, 5, 10] の場合、出力は [1, 3, 7, 12] となります。

アルゴリズムのポイント

この問題は、追加のメモリをほとんど使わずに解決できます。鍵となるのは「符号反転」のテクニックです。配列内の値 v に対応する位置(インデックス v-1)にある要素の符号を反転させることで、「v は出現済み」というマークを付けます。処理後に正の値が残っている位置こそが、欠落している数を表しています。

また、N が配列の長さを超える場合(本記事のように N = 配列サイズ + 4 のケース)は、サイズ4の補助配列を用意し、剰余演算を活用して後半の数値の出現情報を記録します。

処理の手順

1. すべて0で初期化されたサイズ4の補助配列 temp_arr を用意する。
2. i を 0 から配列 A のサイズ未満まで繰り返す。
   • temp := |A[i]| として絶対値を取得する。
   • temp が A のサイズ以下の場合:A[temp - 1] の符号を反転する。
   • temp が A のサイズより大きい場合:
     • temp を A のサイズで割った余りが0でなければ、temp_arr[temp % len(A) - 1] を -1 にする。
     • 余りが0の場合は、temp_arr[(temp % len(A)) + len(A) - 1] を -1 にする。
3. i を 0 から A のサイズ未満まで繰り返し、A[i] > 0 なら i + 1 を表示する。
4. i を 0 から temp_arr のサイズ未満まで繰り返し、temp_arr[i] >= 0 なら len(A) + i + 1 を表示する。

最初のループで小さい側の欠落数が、次のループで大きい側の欠落数がそれぞれ昇順に出力されるため、結果全体も自然にソートされた順序になります。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def find_missing_nums(A) :
    temp_arr = [0]*4
    for i in range(0,len(A)) :
        temp = abs(A[i])
        if (temp <= len(A)) :
            A[temp - 1] = A[temp - 1] * (-1)
        elif (temp > len(A)) :
            if (temp % len(A)) :
                temp_arr[temp % len(A) - 1] = -1
            else :
                temp_arr[(temp % len(A)) +len(A) - 1] = -1
    for i in range(0, len(A) ) :
        if (A[i] > 0) :
            print((i + 1) , end=" ")
    for i in range(0, len(temp_arr)) :
        if (temp_arr[i] >= 0) :
            print((len(A) + i + 1) , end=" ")

A = [2, 8, 4, 13, 6, 11, 9, 5, 10]
find_missing_nums(A)

入力

[2, 8, 4, 13, 6, 11, 9, 5, 10]

出力

1 3 7 12

計算量と注意点

このアルゴリズムは配列を数回走査するだけで済むため、時間計算量は O(N) です。追加で必要なメモリもサイズ4の補助配列のみであり、ソート処理やハッシュセットに頼らずに欠落数を求められる点が大きな特徴です。

ただし、この手法は元の配列の要素の符号を直接書き換えるため、入力データを後続の処理でも使いたい場合は、あらかじめ配列をコピーしておくことをおすすめします。