Codility MissingInteger in Python

发表于 更新于 分类于 ， Disqus：

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(N) O(1)
平均 O(N) O(1)
最差 O(N) O(1)

算法分析

创建检查数组check，遍历数组A的项，若某项的值为整数x，则以整数x作为索引，将check数组对应的项置1。在遍历check数组，寻找值为0时索引的最小值。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
def solution(A):
    # write your code in Python 2.7
    n=len(A)
    max_A=100001
    check=[0]*(max_A+1)
    for i in xrange(n):
        if(A[i]>=0 and A[i]<max_A and check[A[i]-1]==0):
            check[A[i]-1]=1
    for ind in xrange(max_A+1):
        if(check[ind]==0):
            return ind+1
    return -1