时间戳

首页 > 解决方案 > 使用python的频率阵列

python - 使用python的频率阵列

问题描述

我正在尝试解决 codeforces 上的问题，它与频率阵列有关，这是问题的链接https://codeforces.com/group/MWSDmqGsZm/contest/219774/problem/V

这是我的代码：

N , M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
for i in range(1,M+1):
    print(A.count(i))

但是这段代码太慢了，我在测试 2 中超出了时间限制。

标签： python

解决方案

.count()花费 O(N) 时间，并且您正在为输入列表的每个元素执行此操作，导致时间复杂度为 O(N^2)，这就是您获得 TLE 的原因。

您需要dictionary通过仅迭代一次将每个项目的频率存储在 a 中，然后最后打印它们。时间复杂度：O(N + M)

尝试这个。

from collections import Counter
N , M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
c = Counter(A)

for i in range(1,M+1):
    print(c[i])

推荐阅读