)
前言LeetCode 347 要求给定一个整数数组和整数 k返回出现频率最高的 k 个元素。题目不要求结果有序但保证答案唯一在通常的测试数据下前 k 名的频率分界清晰。这道题的价值在于它有三层递进的解法先统计频率再全排序用大小为 k 的堆维护候选或者用桶排序把频率当作下标。三层解法对应三种不同的复杂度取舍是练习“用合适的数据结构换取时间”的好例子。常见误解有两个。第一以为必须返回按频率降序排列的数组题目只要求“前 k 个”顺序不限除非面试官额外要求。第二直接用大顶堆把所有不同元素都放进去得到的结果虽然正确但复杂度是 O(m log m)没有利用“只要前 k 个”这个条件。另一个细节是std::priority_queue默认是最大堆想维护“当前最小的候选”需要显式传入std::greater。本文以 C17 为准使用std::unordered_map统计、std::priority_queue维护候选并给出桶排序版本作为对比。所有复杂度都是量级分析不涉及具体运行时间。一、先统计频率问题的第一步无论后续用什么结构第一步都是把“元素 → 出现次数”统计出来。std::unordered_mapint, int的平均插入和查找是 O(1)适合这个任务// 适用于 C17#include unordered_map#include vectorstd::unordered_mapint, int count_frequency(const std::vectorint nums){std::unordered_mapint, int freq;freq.reserve(nums.size()); // 减少 rehashfor (int value : nums)freq[value];return freq;}freq[value]在键不存在时会插入一个值初始化的 0再自增因此不需要先find。reserve不是必须的但它能减少桶扩容和重新哈希的次数具体收益取决于实现和输入分布不应把它当成性能保证。统计完成后问题变成在一个“元素 → 频率”的集合里找出频率最大的 k 个键。设不同元素个数为 mm ≤ n。接下来的三种做法差别在于如何从 m 个候选中选出 k 个。二、解法一全排序最直观的做法是把所有键值对放进std::vector按频率降序排序取前 k 个// 适用于 C17#include algorithm#include unordered_map#include utility#include vectorstd::vectorint top_k_sort(const std::vectorint nums, int k){std::unordered_mapint, int freq;for (int value : nums)freq[value];std::vectorstd::pairint, int items(freq.begin(), freq.end());std::sort(items.begin(), items.end(),[](const auto a, const auto b) {return a.second b.second;});std::vectorint result;result.reserve(static_caststd::size_t(k));for (int i 0; i k; i)result.push_back(items[static_caststd::size_t(i)].first);return result;}时间复杂度是 O(n m log m)空间 O(m)。当 k 接近 m 时这已经足够好当 k 远小于 m例如从一百万个不同元素里取前十排序做了大量无用功。面试里可以先给出这个版本说明思路再优化到堆。注意比较器只按频率降序没有定义频率相等时的次序。题目不要求稳定因此没问题如果要求“频率相同按元素值升序”需要在比较器里补第二关键字并且保证比较器满足严格弱序。三、解法二大小为 k 的小顶堆要维护“当前最大的 k 个”一个反直觉但有效的做法是用小顶堆堆顶是这 k 个候选里频率最小的。新元素到来时如果它的频率比堆顶大就弹出堆顶、压入新元素否则丢弃。这样堆的大小始终不超过 k最终堆里就是频率最高的 k 个。// 适用于 C17#include functional#include queue#include unordered_map#include utility#include vectorstd::vectorint top_k_heap(const std::vectorint nums, int k){std::unordered_mapint, int freq;for (int value : nums)freq[value];using Item std::pairint, int; // (频率, 元素)// 小顶堆频率小的在堆顶std::priority_queueItem, std::vectorItem, std::greaterItem heap;for (const auto [value, count] : freq){heap.push({count, value});if (static_castint(heap.size()) k)heap.pop();}std::vectorint result;result.reserve(static_caststd::size_t(k));while (!heap.empty()){result.push_back(heap.top().second);heap.pop();}return result;}关键点在std::greaterItemstd::priority_queue默认用std::less得到大顶堆传入std::greater后频率较小的元素优先级更高堆顶就是当前候选中的最小频率。Item是pairint, int比较时先比频率频率相同再比元素值题目不关心并列时的顺序这个次级比较不会影响正确性。复杂度是 O(n m log k)空间 O(m k)。因为 k 通常远小于 mlog k比log m小这是相对全排序的改进。不要把它理解成“堆一定比排序快”当 k 接近 m 时两者量级接近堆还多了每次 push/pop 的常数开销选择要看 k 与 m 的关系。如果要求结果按频率从高到低输出堆弹出顺序是从低到高最后把result反转即可或者改为在弹出时插入到结果头部后者是 O(k²)不推荐。四、解法三桶排序频率有一个天然的上界任何元素的出现次数不超过 n。于是可以把频率当作下标建立 n1 个桶把元素放进对应频率的桶里然后从高频率往低频率扫描凑够 k 个就停。// 适用于 C17#include unordered_map#include vectorstd::vectorint top_k_bucket(const std::vectorint nums, int k){std::unordered_mapint, int freq;for (int value : nums)freq[value];std::vectorstd::vectorint buckets(nums.size() 1);for (const auto entry : freq)buckets[static_caststd::size_t(entry.second)].push_back(entry.first);std::vectorint result;result.reserve(static_caststd::size_t(k));for (int count static_castint(nums.size()); count 1; --count){for (int value : buckets[static_caststd::size_t(count)]){result.push_back(value);if (static_castint(result.size()) k)return result;}}return result;}复杂度是 O(n m)空间 O(n m)。它利用了“频率是 0 到 n 的整数”这一额外信息属于计数排序的思想。桶排序的局限也在这里如果频率不是小整数或者需要按浮点权重排序就不能直接做下标。输入数组的长度决定了桶的数量n 很大时内存占用要纳入考虑。三种解法的对比如下解法时间空间适用场景全排序O(n m log m)O(m)k 接近 m代码最直接小顶堆O(n m log k)O(m k)k 远小于 m通用桶排序O(n m)O(n m)频率为不超过 n 的整数常见坑点❌ 用大顶堆把所有不同元素都压进去再弹出 k 次。✅ 结果正确但复杂度是 O(m log m)维护大小为 k 的小顶堆才能把 log 因子降到 log k。❌ 以为必须按频率降序返回额外做了不必要的排序。✅ 题目只要求集合意义上的前 k 个除非明确要求顺序否则堆的任意弹出顺序都合法。❌ 比较器写成a.second b.second。✅ 排序比较器必须是严格弱序相等时返回 false用而不是否则行为未定义。❌ 桶排序时桶数组只开 n 个频率恰好为 n 的元素越界。✅ 频率范围是 1 到 n桶数组大小为 n1下标 n 合法。❌ 用int和std::size_t混比出现符号警告或意外转换。✅ 统一在边界处显式转换桶下标和result.size()的比较要清楚哪边是整数。❌ 统计频率时对每个元素先find再插入代码冗长且多一次查找。✅freq[value]一次完成“不存在则插入 0、再自增”语义正确。❌ 认为unordered_map的 O(1) 是绝对保证。✅ 那是平均复杂度哈希冲突严重或哈希函数被恶意构造时最坏可退化到 O(n)。对最坏情况有要求时用std::map。❌ 直接修改输入数组来“原地”统计破坏调用方数据。✅ 参数用const std::vectorint需要原地操作时先拷贝或在接口上明确说明会修改。总结步骤做法注意点统计unordered_mapint,int自增平均 O(1)最坏 O(n)选前 k排序全量排序取前 kO(m log m)实现简单选前 k堆小顶堆超过 k 就弹堆顶O(m log k)k 小时占优选前 k桶频率作下标从高往低扫O(nm)依赖频率上界返回顺序不限需要有序时再额外处理这道题的核心不是记住某段代码而是识别出“频率是整数且不超过 n”这个结构信息它让桶排序成为可能而当 k 很小时堆则用更少的空间达到相近的效果。先统计、再选择两步分开写复杂度和边界都会清楚很多。
