如何在Python中以最低时间复杂度返回字符列表中频率最高的两个元素？

时间复杂度结论 #

你当前使用的字典统计方案已经达到了理论最低的时间复杂度，不存在更优的低时间复杂度方案。

• 字符频率统计的理论时间复杂度下界为 O(n)，其中n为输入字符串的长度：你必须遍历所有字符才能得到完整的统计结果，不可能跳过任意一个字符完成统计，因此没有时间复杂度低于*O(n)*的可行方案。

不同实现的差异 #

• 你手写的字典统计逻辑和Python内置的collections.Counter底层逻辑完全一致，都是哈希表计数，时间复杂度均为O(n)，空间复杂度为O(k)，k为输入中不同字符的数量。
• 如果输入字符的取值范围是确定的有限集合（比如仅ASCII字符、仅小写英文字母），可以用固定长度的列表代替哈希表计数，访问的常数开销更低，运行速度会略快，但时间复杂度仍然是O(n)，没有本质下降。

示例：仅统计小写英文字母的列表实现

def count_lower_letters(s: str) -> list[int]:
    res = [0] * 26
    for char in s:
        res[ord(char) - ord('a')] += 1
    return res

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