优化大数据集下的Python代码：解决HackerEarth歌手统计超时问题

问题回顾 #

Bob的播放列表中每首歌对应一位用整数表示的歌手，需统计歌曲数量最多的歌手的个数。比如输入1 1 2 2 3，输出为2（歌手1和2的歌曲数并列最多）。

你的代码能通过小规模测试，但处理大数据集时超时，核心原因是时间复杂度太高：

• 去重时用if i not in result，每次判断是O(n)，整体时间复杂度达O(n²)
• 调用singer_tokens.count(i)统计每个歌手的歌曲数，每次count操作也是O(n)，总时间复杂度为O(mn)（m为不同歌手的数量）

优化方案：用哈希表统计频率（O(n)时间复杂度） #

直接遍历一次列表，用字典统计每个歌手的出现次数，再找出最大次数，最后统计有多少歌手达到这个最大次数即可，全程时间复杂度为O(n)。

方案1：用普通字典实现

singer_tokens = input().split()
count_dict = {}

# 统计每个歌手的歌曲数量
for singer in singer_tokens:
    if singer in count_dict:
        count_dict[singer] += 1
    else:
        count_dict[singer] = 1

# 找出最大的歌曲数量
max_count = max(count_dict.values())

# 统计有多少歌手达到最大数量
result = 0
for cnt in count_dict.values():
    if cnt == max_count:
        result += 1

print(result)

方案2：用collections.Counter简化代码

Python标准库的Counter可以一键完成频率统计，代码更简洁：

from collections import Counter

singer_tokens = input().split()
counts = Counter(singer_tokens)
max_count = max(counts.values())
print(sum(1 for cnt in counts.values() if cnt == max_count))

这两种方案仅需遍历列表一次统计频率，再遍历频率字典两次（找最大值、统计符合条件的数量），大数据集下效率会大幅提升。

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