python - 这个 Max Counters codility 挑战的解决方案有什么问题

Question

因此，我一直在进行有关可调节性的测试，并且有点卡在“最大计数器”测试中(链接 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 counters 都会填充整个数组。

所以我想出了以下解决方案，它似乎适用于小输入，但随机提供中等和大输入的错误结果。

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/