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

所以我一直在进行关于 codility 的测试，并且对“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 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/

最佳答案

一个问题在这里:

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

如果 counters[a - 1] 是 last_update - 1 呢？

关于python - Max Counters codility 挑战的这个解决方案有什么问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20506849/