Codility Maxcountersers in Python

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

算法复杂度分析

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

算法分析

若要达到最差情况下的时间复杂度为O(N+M)，那就意味着不能在A[K] = N + 1时依次将每个counter的值置为当前counters数组的最大值。因为max counter操作的复杂度为O(N)且需要嵌套在复杂度为O(M)的循环中，这样算法的复杂度至少为O(NM)。也就以为着当A[K] = N + 1时，我们不能立即执行max counter操作。借用下惰性求值的概念，只有在真的需要某个counter值的情况的下才执行计算。这就需要建立两个变量，max_A记录当前counters的最大值，lastUpdate记录上一次执行max counter操作时max_A的值。这样只有当A[K] = N + 1时，才把max_A的值赋值给lastUpdate。而当A[i] < N+1时，则要根据lastUpdate的值来更新counter和max_A的值。

最后在返回所counters数组值之前，需要根据lastUpdate的值对每个counter的值进行计算

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(N, A):
    # each element of array A is an integer within the range [1..N + 1]
    # N and M are integers within the range [1..100,000]
    M = len(A)
    max_A = 0
    lastUpdate = 0
    counters=[0]*N
    for i in xrange(M):
        if (A[i]==N+1):
            lastUpdate = max_A
        if (A[i]<N+1):
            if (counters[A[i]-1]<lastUpdate):
                counters[A[i]-1]=lastUpdate+1
                if (counters[A[i]-1]>max_A):
                    max_A=counters[A[i]-1]
            else:
                counters[A[i]-1]=counters[A[i]-1]+1
                if (counters[A[i]-1]>max_A):
                    max_A=counters[A[i]-1]
    for j in xrange(N):
        if (counters[j]<lastUpdate):
            counters[j]=lastUpdate
    return counters
#  time complexity: O(N + M)