Python实现Frequency Array求解Codeforces题目出现超时问题求助

你的代码超时的核心原因是list.count()方法的时间复杂度过高：

• 每次调用A.count(i)都需要完整遍历整个数组A，单次时间复杂度为O(N)
• 外层循环共执行M次，总时间复杂度为O(N×M)，当N、M取值达到10^5量级时，总运算量会超过Python每秒可处理的运算上限，直接触发超时。

采用频率数组预统计的思路，仅遍历原数组1次即可完成所有数字的频率统计，总时间复杂度降至O(N+M)，完全满足题目时间限制，具体实现逻辑如下：

1. 初始化长度为M+1的全零数组，对应存储1~M每个数字的出现频率（索引0无实际意义，仅用来对齐数字和数组下标）
2. 遍历原数组A，每遇到一个数字，就将频率数组对应下标的值加1
3. 最后依次输出频率数组中1~M下标对应的值即可

N, M = map(int, input().split())
A = list(map(int, input().split()))
freq = [0] * (M + 1)
for num in A:
    freq[num] += 1
for i in range(1, M + 1):
    print(freq[i])

内容的提问来源于stack exchange，提问作者Mohamed_Elsharaky