这个Max Counters编码挑战解决方案有什么问题

Question

因此,我一直在进行关于编码的测试,并且对"Max Counters"(位于https://codility.com/demo/take-sample-test/max_counters)感到困惑.我的第一个显而易见的解决方案是:

def solution(N, A):

    counters = N * [0];    

    for a in A:
        if 1 <= a <= N:
            counters[a - 1] += 1;
        elif a == N + 1:
            counters = N * [max(counters)];

    return counters

由于每次调用max计数器填充整个数组,因此工作得很好,但需要花费太多时间.

所以我提出了以下解决方案,似乎适用于小输入,但随机提供中等和大的不正确的结果.

def solution(N, A):

    counters = N * [0];
    current_max = 0;
    last_update = 0;

    for a in A:
        if 1 <= a <= N:
            counters[a - 1] += 1;

            if counters[a - 1] < last_update:
                counters[a - 1] = last_update + 1;

            if counters[a - 1] > current_max:
                current_max = counters[a - 1];

        elif a == N + 1:
            last_update = current_max;

    for i in xrange(len(counters)):
        if counters[i] < last_update:
            counters[i] = last_update;           

    return counters

我似乎无法弄清楚它有什么问题.

编辑:结果 - http://codility.com/demo/results/demoQA7BVQ-NQT/

Answer 1

检查一下(python,获得100分):

每次获得指令将它们全部提升到新的最小值时,秘诀就是不更新所有计数器.这导致每次都涉及每个计数器的操作,并且是~60%得分和100%得分之间的差异.

相反,通过跟踪当前的最小值和最大值来避免这种打击; 为您访问的每个柜台使用和更新它们.

然后,在处理完所有指令之后,因为可能存在自上次更新全部指令以来未用自己的个人更新触摸的计数器,所以通过计数器本身并确保它们处于最小值.

def solution(N, A):
    res = [0] * N
    max_val = 0
    last_update = 0
    n1 = N+1
    for i in A:
        if i < n1:
            if res[i-1] < last_update:
                res[i-1] = last_update

            res[i-1]+=1

            if res[i-1] > max_val:
                max_val = res[i-1]
        else:
            last_update = max_val

    for i in xrange(len(res)):
        if res[i] < last_update:
            res[i] = last_update

    return res

http://codility.com/demo/results/demoF3AMPT-FVN/

Answer 2

这是 @jacoor 解决方案的修改版本，具有更惯用的 python 和变量名称，以及更贴切地反映问题描述的 if 语句条件。

def fast_solution(N, A):
    counters = [0] * N
    max_counter = 0
    last_update = 0

    for K,X in enumerate(A): # O(M)
        if 1 <= X <= N:
            counters[X-1] = max(counters[X-1], last_update)
            counters[X-1] += 1
            max_counter = max(counters[X-1], max_counter)
        elif A[K] == (N + 1):
            last_update = max_counter

    for i in xrange(N): # O(N)
        counters[i] = max(counters[i], last_update)

    return counters

https://codility.com/demo/results/demo6KPS7K-87N/