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

サイズnのnumsと呼ばれる数値のリストがあり、リスト内のすべての数値が区間[1、n]に存在するとします。一部の要素は、2回表示され、他の要素は1回だけ表示される場合があります。リストにないように、[1、n]からすべての番号を見つける必要があります。昇順でソートされた番号を返す必要があります。線形の時間と一定のスペースを必要とする解決策を見つけようとする必要があります。

したがって、入力が[4、4、2、2、6、6]の場合、出力は[1、3、5]になります。

これを解決するには、次の手順に従います-

• arr：=サイズnums + 1の配列で、0で埋めます
• numsの各iについて、
  • arr [i]：=arr [i] + 1
• 欠落：=新しいリスト
• 0からarrのサイズまでの範囲のiについては、
  • arr [i]が0と同じで、iが0と同じでない場合、
    • 行方不明の最後にiを挿入
• 行方不明を返す

理解を深めるために、次の実装を見てみましょう-

例

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]