给定一个N个整数的数组，Python返回在O(N)时间复杂度中不出现的最小正整数(大于0)

I have written two solutions to that problem. The first one is good but I don't want to use any external libraries + its O(n)*log(n) complexity. The second solution "In which I need your help to optimize it" gives an error when the input is chaotic sequences length=10005 (with minus).

我为那个问题写了两个解决方案。第一个很好，但是我不想使用任何外部库加上它的O(n)*log(n)复杂度。当输入为混沌序列长度=10005(带负号)时，第二个解决方案“我需要您的帮助来优化它”会出现错误。

Solution 1:

解决方案1:

from itertools import count, filterfalse 


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

Solution 2:

解决方案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

Note: This was a demo test in codility, solution 1 got 100% and solution 2 got 77 %.
Error in "solution2" was due to:
Performance tests -> medium chaotic sequences length=10005 (with minus) got 3 expected 10000
Performance tests -> large chaotic + many -1, 1, 2, 3 (with minus) got 5 expected 10000

注意:这是一个编译性的演示测试，解决方案1获得100%，解决方案2获得77%。“solution2”中的错误是由于:性能测试——>中混沌序列长度=10005(带-)得到3个预期10000性能测试——>大混沌+多1、1、2、3(带-)得到5个预期10000

1 个解决方案

#1

Testing for the presence of a number in a set is fast in Python so you could try something like this:

在Python中，测试一组数字的存在速度很快，所以您可以尝试以下方法:

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