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]

Arnab Chakraborty

更新于: 2020年10月6日

2K+ 浏览量

开启你的职业生涯

通过完成课程获得认证

开始学习