Python程式查詢1到N之間所有缺失的數字

假設我們有一個名為nums的數字列表，大小為n，其中列表中的所有數字都存在於區間[1, n]中，某些元素可能出現兩次，而其他元素只出現一次。我們需要找到[1, n]中所有不在列表中的數字。我們需要按升序返回這些數字。我們需要嘗試找到一個線性時間和常數空間的解決方案。

因此，如果輸入類似於[4, 4, 2, 2, 6, 6]，則輸出將為[1, 3, 5]。

為了解決這個問題，我們將遵循以下步驟：

  • arr := 一個大小為nums + 1的陣列，並填充0
  • 對於nums中的每個i，執行
    • arr[i] := arr[i] + 1
  • missing := 一個新的列表
  • 對於範圍從0到arr大小的每個i，執行
    • 如果arr[i]與0相同，並且i與0不同，則
      • 在missing的末尾插入i
  • 返回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]

更新於: 2020年10月6日

2K+ 瀏覽量

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告