时间戳

首页 > 解决方案 > 使用 python 的 Codility 课程 MaxCounters 是否可能比 O(N+M) 更好？

python - 使用 python 的 Codility 课程 MaxCounters 是否可能比 O(N+M) 更好？

问题描述

这是我用于 Codility 课程的代码：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，您可以对它们进行两种可能的操作：

给出了一个由 M 个整数组成的非空数组 A。该数组表示连续操作：

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

标签： python

解决方案

编辑：跟进这个答案的评论中的讨论，跟踪最后一个操作以避免在连续的 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 即可。如果不满足第一个条件，则根据练习的定义满足第二个条件

其次，根据我的测试，仅在需要时计算最大值比在所有运行中跟踪它要快得多。这可能是因为 max-operation 只会很少发生，特别是对于 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)

推荐阅读