Python给定一个N个整数的数组A，以O(n)的时间复杂度返回A中没有出现的最小正整数（大于0）

Question

例如：

输入：A = [ 6 4 3 -5 0 2 -7 1 ]

输出：5

因为5是数组中没有出现的最小正整数。

---

我已经为该问题编写了两个解决方案。第一个很好，但我不想使用任何外部库 + 它的 O(n)*log(n) 复杂性。当输入是混沌序列 length=10005（带负号）时，第二个解决方案“我需要你的帮助来优化它”会出错。

解决方案 1：

 from itertools import count, filterfalse

def minpositive(a):
    return(next(filterfalse(set(a).__contains__, count(1))))

解决方案 2：

 def minpositive(a):
    count = 0
    b = list(set([i for i in a if i>0]))
    if min(b, default = 0)  > 1 or  min(b, default = 0)  ==  0 :
        min_val = 1
    else:
        min_val = min([b[i-1]+1 for i, x in enumerate(b) if x - b[i - 1] >1], default=b[-1]+1)

    return min_val

注意：这是 codility 的演示测试，解决方案 1 获得 100%，解决方案 2 获得 77%。

“solution2”中的错误是由于：

性能测试 -> 中等混沌序列长度=10005（带负号）得到 3 个预期的 10000

性能测试 -> large chaotic + many -1, 1, 2, 3 (with minus) got 5 expected 10000

原文由 user8358337 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

在 Python 中测试集合中数字是否存在的速度很快，因此您可以尝试这样的操作：

 def minpositive(a):
    A = set(a)
    ans = 1
    while ans in A:
       ans += 1
    return ans

原文由 Peter de Rivaz 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

大型阵列快速。

 def minpositive(arr):
    if 1 not in arr: # protection from error if ( max(arr) < 0 )
        return 1
    else:
        maxArr = max(arr) # find max element in 'arr'
        c1 = set(range(2, maxArr+2)) # create array from 2 to max
        c2 = c1 - set(arr) # find all positive elements outside the array
        return min(c2)

原文由 Dimdimy4 发布，翻译遵循 CC BY-SA 4.0 许可协议