如何降低统计列表重复元素总出现次数代码的时间复杂度

你的代码时间复杂度过高的核心原因是构建统计字典的逻辑是*O(n²)*时间复杂度：

• 你对列表里的每一个元素都调用了your_list.count(item)，该方法每次都会完整遍历一次整个列表统计匹配次数，当输入列表长度很大时，耗时会呈指数级增长
• 后续多次遍历统计结果的列表也属于冗余操作，进一步增加了不必要的耗时

只需要对输入列表做1次遍历完成频率统计，再对统计结果做1次遍历计算总和，整体时间复杂度可以降到O(n)，完全可以应对大输入量的测试用例。

可以直接用Python标准库collections中的Counter工具完成高效的频率统计，它的底层实现就是单次遍历列表统计次数，性能远高于自行循环调用count方法。

使用Counter的极简实现：

from collections import Counter

your_list = input().split()
counts = Counter(your_list)
total = sum(v for v in counts.values() if v > 1)
print(total if total != 0 else -1)

如果不想引入标准库依赖，也可以手动实现统计逻辑，性能同样为O(n)：

your_list = input().split()
count_dict = {}
for item in your_list:
    count_dict[item] = count_dict.get(item, 0) + 1

total = 0
for v in count_dict.values():
    if v > 1:
        total += v

print(total if total != 0 else -1)

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