本文深入剖析 leetcode 347 题“前 k 个高频元素”中桶排序解法为何具有线性时间复杂度 o(n)，关键在于内外双层循环的总迭代次数被严格限制在 k 次以内，而非 k×n。
本文深入剖析 leetcode 347 题“前 k 个高频元素”中桶排序解法为何具有线性时间复杂度 o(n)，关键在于内外双层循环的总迭代次数被严格限制在 k 次以内，而非 k×n。
在解决“Top K Frequent Elements”问题时，相比堆排序（O(n log k)）或全排序（O(n log n)），桶排序（Bucket Sort）方案提供了真正线性的最坏时间复杂度——O(n)。其核心不在于“每层循环单独看是 O(n)”，而在于两层嵌套循环的总体执行次数存在紧致上界。
以下是该算法的标准实现（已修正原提问中的语法错误）：
from typing import List, Dict, DefaultDict
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# Step 1: 统计频次 —— O(n)
count: Dict[int, int] = {}
for num in nums:
count[num] = count.get(num, 0) + 1
# Step 2: 构建频次桶（索引 i 表示频次，bucket[i] 存储所有出现 i 次的数字）—— O(n)
# 最大可能频次为 len(nums)，故桶大小为 n+1
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
buckets[freq].append(num)
# Step 3: 从高频到低频收集结果 —— 关键：总追加次数 ≤ k
result = []
# 逆序遍历桶（从最高频次开始）
for freq in range(len(buckets) - 1, 0, -1):
for num in buckets[freq]:
result.append(num)
if len(result) == k:
return result
return result✅ 时间复杂度正确分析如下：
- 第一步频次统计：遍历 nums 一次 → O(n)
- 第二步构建桶：遍历哈希表 count（最多 n 个不同元素）→ O(n)
- 第三步收集结果：这是常被误解的部分。注意：
- 外层 for freq in ... 最多迭代 n+1 次（桶数量），但不代表每次都会进入内层循环；
- 内层 for num in buckets[freq] 每执行一次 result.append(num)，就向结果添加一个新元素；
- 一旦 len(result) == k，函数立即 return，整个过程至多执行 k 次 append；
- 因此，内层循环的总迭代次数（即所有 num 被访问的次数）严格 ≤ k；
- 外层循环虽可能扫描多个桶，但只要累计选出 k 个数就终止，实际扫描的桶数远小于 n（尤其当高频元素集中时）。
综上，第三步总开销为 O(n + k)：外层循环最多检查 n+1 个桶（O(n)），内层循环总共只处理 k 个元素（O(k)）。由于 k ≤ n（题目要求取前 k 个，k 不会超过数组长度），因此 O(n + k) = O(n)。
⚠️ 常见误区澄清：
- ❌ “外层循环 O(n)，内层循环每轮 O(n)，所以 O(n²)” —— 错误。内层不是每轮都跑满，且不重置、不重复计数；
- ❌ “最坏情况是所有元素频次为 1，要遍历到 bucket[1]，此时内层循环跑 n 次” —— 即便如此，也仅在 freq=1 这一轮内层执行 ≤ k 次（因遇到第 k 个就返回），不会遍历全部 n 个元素；
- ✅ 正确视角：将内层循环视为一个「全局资源消耗器」，它总共只被允许执行 k 次操作，与外层结构无关。
? 总结：
桶排序解法的 O(n) 时间复杂度成立，根本原因在于结果收集阶段受 k 严格截断，使得看似嵌套的双重循环实则具备线性总工作量。这一设计体现了“用空间换确定性时间”的经典权衡——O(n) 空间（桶数组）换取 O(n) 稳定时间性能，非常适合频次类 Top-K 场景。
