Codility Maxcountersers in Python

  • Shuwei Zhang & Jinhai ZHOU
  • 4 Minutes
  • 2017年6月2日

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 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的值来更新countermax_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)