Codility FrogRiverOne in Python

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

算法复杂度分析

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

最优情况在输入数组长度小于河宽X下达成

算法分析

依次读取输入数组的项，当读取过的项的集合包含1到X在内的所有整数时，输出当前项的数组索引。对于记录读取过的项的集合，可以用一个长度为X+1的check数组来记录。若读取了整数z，就把整数z作为索引，将对应的项置1。对于判断读取过的项的集合是否包含1到X在内的所有整数，我们都可以遍历check数组，检查索引1到X对应的项是否全部为1，如果不是，则说明我们还没有包含1到X在内的所有整数。但是这样，该判断算法需要遍历check数组，复杂度为O(X)。不过有一个小技巧可以将该判断算法降为O(1)，那就是在check数组的基础上，再使用step_left变量来记录还需要读取多少个不同的整数后读取过的项的集合才能包含1到X在内的所有整数。若读取了整数z，除了把整数z作为索引，将对应的项置1外，还要根据条件来更新step_left的值。此时，检查算法只需要判断step_left是否为0即可得知读取过的项的集合是否包含1到X在内的所有整数了。

源代码

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