企业官网建设流程全解析

前言

LeetCode 347 要求给定一个整数数组和整数 k，返回出现频率最高的 k 个元素。题目不要求结果有序，但保证答案唯一（在通常的测试数据下，前 k 名的频率分界清晰）。这道题的价值在于它有三层递进的解法：先统计频率再全排序，用大小为 k 的堆维护候选，或者用桶排序把频率当作下标。三层解法对应三种不同的复杂度取舍，是练习“用合适的数据结构换取时间”的好例子。

常见误解有两个。第一，以为必须返回按频率降序排列的数组；题目只要求“前 k 个”，顺序不限，除非面试官额外要求。第二，直接用大顶堆把所有不同元素都放进去，得到的结果虽然正确，但复杂度是 O(m log m)，没有利用“只要前 k 个”这个条件。另一个细节是std::priority_queue默认是最大堆，想维护“当前最小的候选”需要显式传入std::greater。

本文以 C++17 为准，使用std::unordered_map统计、std::priority_queue维护候选，并给出桶排序版本作为对比。所有复杂度都是量级分析，不涉及具体运行时间。

一、先统计频率：问题的第一步

无论后续用什么结构，第一步都是把“元素 → 出现次数”统计出来。std::unordered_map<int, int>的平均插入和查找是 O(1)，适合这个任务：

// 适用于 C++17
#include <unordered_map>
#include <vector>

std::unordered_map<int, int> count_frequency(const std::vector<int>& nums)
{
std::unordered_map<int, int> freq;
freq.reserve(nums.size()); // 减少 rehash
for (int value : nums)
++freq[value];
return freq;
}

freq[value]在键不存在时会插入一个值初始化的 0，再自增，因此不需要先find。reserve不是必须的，但它能减少桶扩容和重新哈希的次数；具体收益取决于实现和输入分布，不应把它当成性能保证。

统计完成后，问题变成：在一个“元素 → 频率”的集合里，找出频率最大的 k 个键。设不同元素个数为 m，m ≤ n。接下来的三种做法，差别在于如何从 m 个候选中选出 k 个。

二、解法一：全排序

最直观的做法是把所有键值对放进std::vector，按频率降序排序，取前 k 个：

// 适用于 C++17
#include <algorithm>
#include <unordered_map>
#include <utility>
#include <vector>

std::vector<int> top_k_sort(const std::vector<int>& nums, int k)
{
std::unordered_map<int, int> freq;
for (int value : nums)
++freq[value];

std::vector<std::pair<int, int>> items(freq.begin(), freq.end());
std::sort(items.begin(), items.end(),
[](const auto& a, const auto& b) {
return a.second > b.second;
});

std::vector<int> result;
result.reserve(static_cast<std::size_t>(k));
for (int i = 0; i < k; ++i)
result.push_back(items[static_cast<std::size_t>(i)].first);

return result;
}

时间复杂度是 O(n + m log m)，空间 O(m)。当 k 接近 m 时，这已经足够好；当 k 远小于 m（例如从一百万个不同元素里取前十），排序做了大量无用功。面试里可以先给出这个版本说明思路，再优化到堆。

注意比较器只按频率降序，没有定义频率相等时的次序。题目不要求稳定，因此没问题；如果要求“频率相同按元素值升序”，需要在比较器里补第二关键字，并且保证比较器满足严格弱序。

三、解法二：大小为 k 的小顶堆

要维护“当前最大的 k 个”，一个反直觉但有效的做法是用小顶堆：堆顶是这 k 个候选里频率最小的。新元素到来时，如果它的频率比堆顶大，就弹出堆顶、压入新元素；否则丢弃。这样堆的大小始终不超过 k，最终堆里就是频率最高的 k 个。

// 适用于 C++17
#include <functional>
#include <queue>
#include <unordered_map>
#include <utility>
#include <vector>

std::vector<int> top_k_heap(const std::vector<int>& nums, int k)
{
std::unordered_map<int, int> freq;
for (int value : nums)
++freq[value];

using Item = std::pair<int, int>; // (频率, 元素)

// 小顶堆：频率小的在堆顶
std::priority_queue<Item, std::vector<Item>, std::greater<Item>> heap;

for (const auto& [value, count] : freq)
{
heap.push({count, value});
if (static_cast<int>(heap.size()) > k)
heap.pop();
}

std::vector<int> result;
result.reserve(static_cast<std::size_t>(k));
while (!heap.empty())
{
result.push_back(heap.top().second);
heap.pop();
}
return result;
}

关键点在std::greater<Item>：std::priority_queue默认用std::less，得到大顶堆；传入std::greater后，频率较小的元素优先级更高，堆顶就是当前候选中的最小频率。Item是pair<int, int>，比较时先比频率，频率相同再比元素值；题目不关心并列时的顺序，这个次级比较不会影响正确性。

复杂度是 O(n + m log k)，空间 O(m + k)。因为 k 通常远小于 m，log k比log m小，这是相对全排序的改进。不要把它理解成“堆一定比排序快”：当 k 接近 m 时，两者量级接近，堆还多了每次 push/pop 的常数开销；选择要看 k 与 m 的关系。

如果要求结果按频率从高到低输出，堆弹出顺序是从低到高，最后把result反转即可，或者改为在弹出时插入到结果头部（后者是 O(k²)，不推荐）。

四、解法三：桶排序

频率有一个天然的上界：任何元素的出现次数不超过 n。于是可以把频率当作下标，建立 n+1 个桶，把元素放进对应频率的桶里，然后从高频率往低频率扫描，凑够 k 个就停。

// 适用于 C++17
#include <unordered_map>
#include <vector>

std::vector<int> top_k_bucket(const std::vector<int>& nums, int k)
{
std::unordered_map<int, int> freq;
for (int value : nums)
++freq[value];

std::vector<std::vector<int>> buckets(nums.size() + 1);
for (const auto& entry : freq)
buckets[static_cast<std::size_t>(entry.second)].push_back(entry.first);

std::vector<int> result;
result.reserve(static_cast<std::size_t>(k));

for (int count = static_cast<int>(nums.size()); count >= 1; --count)
{
for (int value : buckets[static_cast<std::size_t>(count)])
{
result.push_back(value);
if (static_cast<int>(result.size()) == k)
return result;
}
}
return result;
}

复杂度是 O(n + m)，空间 O(n + m)。它利用了“频率是 0 到 n 的整数”这一额外信息，属于计数排序的思想。桶排序的局限也在这里：如果频率不是小整数，或者需要按浮点权重排序，就不能直接做下标。输入数组的长度决定了桶的数量，n 很大时内存占用要纳入考虑。

三种解法的对比如下：

常见坑点

1. 
   
2. ❌ 用大顶堆把所有不同元素都压进去，再弹出 k 次。
3. 
   

✅ 结果正确，但复杂度是 O(m log m)；维护大小为 k 的小顶堆才能把 log 因子降到 log k。

1. 
   
2. ❌ 以为必须按频率降序返回，额外做了不必要的排序。
3. 
   

✅ 题目只要求集合意义上的前 k 个；除非明确要求顺序，否则堆的任意弹出顺序都合法。

1. 
   
2. ❌ 比较器写成a.second >= b.second。
3. 
   

✅ 排序比较器必须是严格弱序，相等时返回 false；用>而不是>=，否则行为未定义。

1. 
   
2. ❌ 桶排序时桶数组只开 n 个，频率恰好为 n 的元素越界。
3. 
   

✅ 频率范围是 1 到 n，桶数组大小为 n+1，下标 n 合法。

1. 
   
2. ❌ 用int和std::size_t混比，出现符号警告或意外转换。
3. 
   

✅ 统一在边界处显式转换；桶下标和result.size()的比较要清楚哪边是整数。

1. 
   
2. ❌ 统计频率时对每个元素先find再插入，代码冗长且多一次查找。
3. 
   

✅++freq[value]一次完成“不存在则插入 0、再自增”，语义正确。

1. 
   
2. ❌ 认为unordered_map的 O(1) 是绝对保证。
3. 
   

✅ 那是平均复杂度；哈希冲突严重或哈希函数被恶意构造时，最坏可退化到 O(n)。对最坏情况有要求时用std::map。

1. 
   
2. ❌ 直接修改输入数组来“原地”统计，破坏调用方数据。
3. 
   

✅ 参数用const std::vector<int>&；需要原地操作时先拷贝，或在接口上明确说明会修改。

总结

这道题的核心不是记住某段代码，而是识别出“频率是整数且不超过 n”这个结构信息：它让桶排序成为可能；而当 k 很小时，堆则用更少的空间达到相近的效果。先统计、再选择，两步分开写，复杂度和边界都会清楚很多。