python - 是否有一个 python 函数返回列表中没有出现的第一个正整数？

Question

我正在尝试设计一个函数，给定一个包含 N 个整数的数组 A，返回 A 中没有出现的最小正整数(大于 0)。

此代码工作正常但复杂度较高，是否有其他解决方案可以降低复杂度？

注意:10000000 数是数组 A 中的整数范围，我尝试了 sort 功能，但它是否降低了复杂性？

def solution(A):
    for i in range(10000000):
        if(A.count(i)) <= 0:
            return(i)

Answer 1

以下是O(n logn) :

a = [2, 1, 10, 3, 2, 15]

a.sort()
if a[0] > 1:
  print(1)
else:
  for i in range(1, len(a)):
    if a[i] > a[i - 1] + 1:
      print(a[i - 1] + 1)
      break

如果您不喜欢 1 的特殊处理，您可以只将零附加到数组，并使用相同的逻辑处理两种情况:

a = sorted(a + [0])
for i in range(1, len(a)):
  if a[i] > a[i - 1] + 1:
    print(a[i - 1] + 1)
    break

注意事项(修复起来都很简单，都留给读者作为练习):

• 两个版本都不处理空输入。
• 代码假定输入中没有负数。