Codility MissingInteger in Python

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 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