Codility 4.3 Maxcounters

Task description
You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,
max counter − all counters are set to the maximum value of any counter.
A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
if A[K] = N + 1 then operation K is max counter.
For example, given integer N = 5 and array A such that:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4
the values of the counters after each consecutive operation will be:

    (0, 0, 1, 0, 0)
    (0, 0, 1, 1, 0)
    (0, 0, 1, 2, 0)
    (2, 2, 2, 2, 2)
    (3, 2, 2, 2, 2)
    (3, 2, 2, 3, 2)
    (3, 2, 2, 4, 2)
The goal is to calculate the value of every counter after all operations.

Write a function:

def solution(N, A)

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

    A[0] = 3
    A[1] = 4
    A[2] = 4
    A[3] = 6
    A[4] = 1
    A[5] = 4
    A[6] = 4
the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000];
each element of array A is an integer within the range [1..N + 1].

这道题有一种O（N*M）的解法，for的复杂度是O(M)，for里面l的赋值的复杂度是O(N)。这个通过率是66%。

def solution(N, A):
    # write your code in Python 3.6
    l = [0]*N
    count_max =0
    
    for i in A:
        if i!=N+1:
            l[i-1]+=1
        else:
            l = [max(l)]*N
    return l

还有一种是O(M*N)的解题方法：
不用max(l)这个语句，而是用一个变量来存储最大值，这个通过率是88%。

def solution(X, A):
    # write your code in Python 3.6
    l = [0]*X
    count_max =0
    
    for i in A:
        if i!=X+1:
            l[i-1]+=1  
            if count_max<l[i-1]:
                count_max = l[i-1]
        else:
            l = [count_max]*X
    return l

时间复杂度是O(M+N)的解法。当最大值获得了，先不改变list的值，而是在后续的每一步中改变。if max_counter > l[i-1]: l[i-1] = max_counter这个语句就是保证出现在A里面的每个元素的值先被改变成最大count，再在此基础上加1。最后的for循环，则是将没出现在A里面的元素被改变成最大count。这种解法来自https://codesays.com/2014/solution-to-max-counters-by-codility/

A =  [3,4,4,6,3,4,5]
N = 5
l = [0]*N   
max_counter = 0  
current_max = 0   
for i in A:
    if i!=N+1:
        if max_counter > l[i-1]:
            l[i-1] = max_counter
        l[i-1] += 1
        if current_max < l[i-1]:
            current_max = l[i-1]
    else:
        max_counter = current_max
    print(l)
    
for i in range(0,N):
    if l[i] < max_counter:
        l[i] = max_counter
print(l)