给定一个整数列表，要求返回出现次数最多的前 K 个元素，这是算法题中的经典场景，也是搜索热词、日志统计等业务里的基础操作。最直接的思路是把所有元素按频率排序再取前 K 个，但如果数据规模较大，全量排序会带来不必要的性能开销。更合理的做法通常分成两步：先遍历一次数据得到每个元素的出现次数，再基于频率信息提取最高的 K 个。本文会从频率统计、Top K 筛选、常见错误和工程优化几个角度展开，并用 Python 给出可运行的具体实现。
频率统计：Counter 到底做了什么
频率统计是整道题的第一步，核心思想是用哈希表把每个元素映射到它出现的次数。手动实现时，可以创建一个空字典，遍历列表，每次用 freq.get(num, 0) 取出当前次数并加一。这段代码的时间复杂度是 O(n)，空间复杂度是 O(m)，其中 m 是不同元素的数量。它不会因为列表很长而退化，只要哈希表没有严重冲突，实际表现非常稳定。
Python 标准库里的 collections.Counter 可以直接完成这件事。它内部继承自 dict，同样满足哈希表的复杂度特征。传入列表后，Counter(nums) 会统计每个元素的出现次数，调用 most_common(k) 就能直接返回频率最高的 k 个键值对。很多人以为 most_common 内部一定做了全量排序，实际上在较新的 CPython 版本中，它使用堆来维护 top K，复杂度大约是 O(n log k)，但在某些场景下也可能退回到排序。因此如果只是做一次简单统计，直接用 Counter 最省事；如果要精确控制复杂度，还是建议自己写后续的 top K 逻辑。
边界条件需要提前处理。比如列表为空时，Counter 本身不会报错，但 most_common(k) 在 k 为 0 或负数时可能返回空列表，这符合预期；如果 k 大于不同元素的总数，返回值会少于 k，调用方不应该假设结果长度一定等于 k。更稳妥的写法是先做 k = min(k, len(freq))，避免后续依赖索引出错。
from collections import Counter
def top_k_frequent_counter(nums, k):
freq = Counter(nums)
# 限制 k 不超过不同元素的个数
k = min(k, len(freq))
return [num for num, count in freq.most_common(k)]
Top K 筛选的三种实现
拿到频率字典后，下一步是从中选出频率最高的 k 个元素。最直观的方法是排序法：把 freq.items() 转换成列表，按照频率降序排列，再截取前 k 个元素。这种写法只有一行代码，容易理解和调试，在小数据量下完全够用。但它的时间复杂度是 O(n log n)，因为 Python 的排序算法需要对所有元素做比较。当输入长度从一万变成一千万时，排序带来的额外时间会明显影响接口响应。
def top_k_frequent_sort(nums, k):
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
sorted_items = sorted(freq.items(), key=lambda item: -item[1])
return [num for num, count in sorted_items[:k]]
更高效的做法是使用堆，尤其是当 k 远小于 n 时，优势更加明显。heapq.nlargest(k, freq.items(), key=lambda item: item[1]) 可以快速返回频率最高的 k 个元素。它内部会维护一个大小为 k 的最小堆，只保留当前遇到的前 k 个高频元素。每来一个新元素，如果它比堆顶频率高，就替换堆顶，再调整堆。这样复杂度可以降到 O(n log k)。手写固定容量最小堆的代码也不复杂：将 (count, num) 压入堆，当堆大小超过 k 时弹出堆顶，最终堆里留下的就是频率最高的 k 个元素。
import heapq
def top_k_frequent_heap(nums, k):
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
heap = []
for num, count in freq.items():
heapq.heappush(heap, (count, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for count, num in heap]
第三种是桶排序。由于单个元素的最大出现次数不会超过列表长度 n，所以可以创建一个长度为 n + 1 的桶数组，桶的下标表示出现次数，桶内存放具有该频率的所有元素。统计完频率后，把元素放进对应桶中，再从高频率到低频率依次收集，直到凑满 k 个即可。桶排序的总复杂度是 O(n)，但它需要额外的 O(n) 空间来存放桶。当 n 非常大且 k 较小时，空间开销可能偏大，不过它不存在堆调整中的对数项，适合对时间要求极高、频率上界明确的场景。
def top_k_frequent_bucket(nums, k):
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
bucket = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
bucket[count].append(num)
result = []
for count in range(len(bucket) - 1, -1, -1):
result.extend(bucket[count])
if len(result) >= k:
return result[:k]
return result
常见错误解析：元组顺序、并列频次与参数边界
第一个常见错误出现在排序或比较字典时，误以为 sorted(freq) 会按频率排序。字典默认的可迭代对象是键，所以 sorted(freq) 实际上是对元素值本身排序，而不是按出现次数排序。如果题目输入的是整数列表，结果会按整数大小升序返回，完全偏离目标。正确的写法必须是传入 freq.items()，并使用 key=lambda item: item[1] 来指定比较频率。
# 错误示范：直接对字典排序相当于按元素值排序
freq = {3: 4, 1: 2, 2: 1}
sorted(freq) # 结果是 [1, 2, 3]，而不是按频率
第二个错误和堆元组的比较顺序有关。如果把元素值放在元组第一位，比如 (num, count) 入堆，Python 会先比较两个元组的第一个元素 num，再比较第二个元素 count。这样堆的排序依据就变成了元素值大小，而不是频率高低。即使后续逻辑看似正确，最终结果也会错。使用 (count, num) 入堆也有一个细节：当 count 相同时，Python 会自动比较 num，这虽然不一定会导致错误，但如果题目要求相同频率的元素按元素值升序或降序排列，就需要显式处理，不能依赖默认行为。
# 错误示范：元组第一位写成 num，比较时先看 num 大小 heap = [] heapq.heappush(heap, (num, count)) # 这会导致堆按 num 排序，而不是按 count 排序
第三个常见错误是忽略 k 超过不同元素数量的情况。当 k > len(freq) 时，如果代码中还有按 k 截断或访问第 k 个元素的操作，就容易出现索引越界或结果长度不足的问题。另一个细节是频率并列时的稳定性。排序法和堆法在 count 相同的情况下，返回元素的顺序可能不同，而不同版本的 Python 也可能有差异。如果题目没有明确要求顺序，这些差异不影响正确性；如果要求按照元素大小稳定输出，可以在排序键中额外加入元素值，例如 key=lambda item: (-item[1], item[0]) 表示先按频率降序，再按元素值升序。
# 修正：先按频率降序，再按元素值升序，避免并列时顺序不稳定
def top_k_frequent_stable(nums, k):
freq = {}
for num in nums:
freq[num] = freq.get(num, 0) + 1
sorted_items = sorted(
freq.items(),
key=lambda item: (-item[1], item[0])
)
return [num for num, count in sorted_items[:k]]
性能对比与选型建议
三种方法在不同数据规模下表现差异很大。排序法最容易实现，但复杂度最高；堆法在 k 较小时能显著减少比较次数，是最常用的折中方案；桶排序理论上最快，但空间占用也最明显。实际工程中，如果只是处理几千条数据，渲染结果通常不会成为瓶颈，直接使用 Counter.most_common 或排序法即可。如果面对的是海量日志或流式数据，则要优先考虑堆，必要时引入近似算法降低内存。
下面这段基准测试可以直观感受排序法和堆法的差距。测试数据为一百万个随机整数，k 设为 10。排序法需要对所有出现过的元素排序，而堆法只维护长度为 10 的最小堆，时间差异会随 n 增大进一步拉开。需要注意的是，基准测试结果受机器环境、Python 版本和元素分布影响，实际项目应以自己的数据做验证。
import random
import time
from collections import Counter
import heapq
nums = [random.randint(1, 100000) for _ in range(1000000)]
freq = Counter(nums)
k = 10
start = time.perf_counter()
sorted(freq.items(), key=lambda item: -item[1])[:k]
print("排序法耗时", time.perf_counter() - start)
start = time.perf_counter()
heapq.nlargest(k, freq.items(), key=lambda item: item[1])
print("堆法耗时", time.perf_counter() - start)
如果数据规模继续扩大，单机内存可能无法存放完整的频率字典，这时可以考虑分片统计或使用 Count-Min Sketch 这类近似结构。Count-Min Sketch 通过多个哈希函数在有限空间内估计元素频率，牺牲一定精度换取常数级的内存占用，常被用在流式计算和推荐系统的热门统计中。不过对于大多数 Python 面试题和常规业务需求，先掌握 Counter、堆和桶排序这三种思路，已经足够覆盖常见场景，并且能有效避免元组顺序和边界条件带来的坑。