Pythonで1からNまでの範囲の欠落している数字をすべて見つけるプログラム

サイズ n の整数リスト nums があり、リスト内のすべての数値は区間 [1, n] に含まれているとします。このとき、一部の要素は2回出現し、その他は1回だけ出現します。この課題では、[1, n] の範囲のうちリストに存在しない数値（欠落している数字）をすべて見つけ、昇順に並べて返す必要があります。できるだけ線形時間 O(n) で動作する効率的な解法を目指しましょう。

例えば、入力が [4, 4, 2, 2, 6, 6] の場合、出力は [1, 3, 5] となります。

解法のアプローチ

この問題は「カウント配列（各数値の出現回数を記録する配列）」を使うことでシンプルに解決できます。手順は以下のとおりです。

• ステップ1： サイズが len(nums) + 1 の配列 arr を作成し、すべての要素を 0 で初期化します。
• ステップ2： リスト nums 内の各数値 i について、arr[i] の値を 1 ずつ増やします。これにより、各数値の出現回数が記録されます。
• ステップ3： 結果を格納するための空のリスト missing を用意します。
• ステップ4： インデックス i を 0 から arr の末尾まで走査し、arr[i] が 0（＝一度も出現していない）かつ i が 0 でない場合、i を missing の末尾に追加します。
• ステップ5： 最後に missing を返します。

それでは、実際の実装例を見て理解を深めましょう。

実装例

class Solution:
   def solve(self, nums):
      arr = [0]*(len(nums)+1)
      for i in nums:
         arr[i] += 1
      missing = []
      for i in range(len(arr)):
         if arr[i] == 0 and i != 0:
            missing.append(i)
      return missing
ob = Solution()
print(ob.solve([4, 4, 2, 2, 6, 6]))

入力

[4, 4, 2, 2, 6, 6]

出力

[1, 3, 5]

計算量のポイント

この解法では、リストの走査とカウント配列の確認の両方に O(n) かかるため、全体の時間計算量は O(n) です。ただし、補助配列 arr を使用しているため、空間計算量は O(n) となります。もし「追加メモリを使わない（定数空間）」という要件を厳密に満たしたい場合は、各値 v を参照した際に nums[v-1] の符号を負に反転させるテクニックなどを活用することで、追加の配列なしで欠落した数字を検出することも可能です。