python - 对于使用 python 的 Codility 类(class) MaxCounters，是否有可能比 O(N+M) 更好？

Question

这是我在 Codility 类(class)中使用的代码:MaxCounters

def solution(N, A):
    counters = [0] * N
    max_c = 0
    for el in A:
        if el >= 1 and el <= N:
            counters[el-1] += 1
            max_c = max(counters[el-1], max_c)
        elif el > N:
            counters = [max_c] * N
    return counters

每个测试都通过，但最后一个(“所有 max_counter 操作”)在 7 秒后超时，因此结果仅为 88%，时间复杂度为 O(N+M)。

是否可以使用Python提高算法的时间复杂度并获得100%的测试结果？

MaxCounters 任务

你有 N 个计数器，初始设置为 0，你可以对它们进行两种可能的操作:

• increase(X) - 计数器 X 增加 1，
• max counter - 所有计数器都设置为任何计数器的最大值。

给定一个非空数组 A，其中包含 M 个整数。这个数组代表连续的操作:

• 如果 A[K] = X，使得 1 ≤ X ≤ N，则操作 K 为 increase(X)，
• 如果 A[K] = N + 1 则操作 K 是最大计数器。

为以下假设编写一个有效的算法:

• N和M为[1..100,000]范围内的整数；
• 数组A的每个元素都是[1..N + 1]范围内的整数。

Answer 1

编辑:跟进这个答案的评论中的讨论，跟踪最后的操作以避免在连续的 max_counter 操作中不必要地重置数组是实现目标的关键。以下是不同的解决方案(一个跟踪最大值，第二个按需计算最大值)在实现该更改时的样子:

def solution(N, A):
    counters = [0] * N
    max_c = 0
    last_was_max = False
    for el in A:
        if el <= N:
            counters[el - 1] += 1
            max_c = max(counters[el - 1], max_c)
            last_was_max = False
        elif not last_was_max:
            counters = [max_c] * N
            last_was_max = True
    return counters


def solution2_1(N, A):
    counters = [0] * N
    last_was_max = False
    for el in A:
        if el <= N:
            counters[el - 1] += 1
            last_was_max = False
        elif not last_was_max:
            counters = [max(counters)] * N
            last_was_max = True
    return counters

我不知道提交中使用了哪个实现。

---

首先，您在 if 条件上浪费了一些时间:没有必要检查整数是否大于或等于 1，这是练习中给出的。然后，无需评估第二个 elif 语句，只需在那里寻找 else 即可。如果不满足第一个条件，则根据练习的定义满足第二个条件

其次，根据我的测试，仅在需要时计算最大值比在所有运行中跟踪它要快得多。这可能是因为最大操作很少发生，特别是对于大的 M 值，因此你浪费时间多次跟踪东西而不是在运行期间只计算最大值几次。

针对@Nearoo 的评论，重新分配数组似乎确实改变了物理地址，但根据我运行的一些测试，重新分配无论如何比 for 循环快得多。

def solution2(N, A):
    counters = [0] * N
    for el in A:
        if el <= N:
            counters[el - 1] += 1
        else:
            counters = [max(counters)] * N
    return counters

在使用不同种子值的多次测试运行中，我提出的这个解决方案比您的解决方案高出 2-3 倍。这是要重现的代码:

import random

random.seed(101)
N = random.randint(1, 100000)
M = random.randint(1, 100000)
A = [random.randint(1, N + 1) for i in range(M)]

%timeit solution(N,A)
>>> 11.7 ms ± 805 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit solution2(N,A)
>>> 3.63 ms ± 169 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)