C++如何在数组中查找出现频率前K高的元素-C++-PHP中文网

可行，但需先将 unordered_map 的键值对拷贝至 vector 等支持随机访问的容器再排序，因其迭代器为前向迭代器，不支持 sort 直接调用。

c++如何在数组中查找出现频率前k高的元素

用 `std::unordered_map` 统计频次再按值排序是否可行？

可行，但容易踩坑：直接对 std::unordered_map 的迭代器做 std::sort 会编译失败，因为其迭代器是前向迭代器，不支持随机访问。必须先拷贝到支持随机访问的容器（如 std::vector）里。

常见错误写法：
std::sort(map.begin(), map.end(), ...) → 编译报错：invalid operands to binary expression

正确做法是提取键值对：

std::vector<:pair int>> freqs;
freqs.reserve(map.size());
for (const auto& p : map) {
    freqs.emplace_back(p.first, p.second);
}
std::sort(freqs.begin(), freqs.end(), [](const auto& a, const auto& b) {
    return a.second > b.second; // 降序：频次高在前
});
</:pair>

注意：如果 K 很小（比如 K=10，数组长度百万），全量排序浪费性能——此时应换堆。

为什么推荐用 `std::priority_queue` 做 Top-K？

当 K 远小于数组长度 N 时，堆方法时间复杂度是 O(N log K)，比排序的 O(N log N) 更优；空间也只占 O(K)。

关键点：

定义最小堆（不是最大堆）：用 std::greater 或自定义比较，让堆顶是当前最小频次，方便淘汰
插入时若堆大小超 K，弹出堆顶（最小频次元素），保证堆中始终是频次最高的 K 个
最后结果需倒序输出（因为堆顶是最小的，而我们要从高到低排列）

示例核心逻辑：

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

std::priority_queue<:pair int>, std::vector<:pair int>>,
                   std::greater<:pair int>>> min_heap;
for (const auto& p : freq_map) {
    min_heap.push({p.second, p.first}); // 频次在前，便于按频次比较
    if (min_heap.size() > k) min_heap.pop();
}
std::vector<int> result;
while (!min_heap.empty()) {
    result.push_back(min_heap.top().second);
    min_heap.pop();
}
std::reverse(result.begin(), result.end()); // 调整为频次降序
</int></:pair></:pair></:pair>

遇到重复元素和相同频次怎么处理？

题目只要求“频率前 K 高”，没指定相同频次时如何排序。实际中常有两类需求：

任意选 K 个（默认行为）：上面堆或排序方法都满足
相同频次按元素值升序/降序：需在比较函数中加二级条件，例如排序时：a.second != b.second ? a.second > b.second : a.first

注意：堆方式加二级排序更麻烦，因为 std::priority_queue 比较逻辑固定，一旦加了二级条件，就无法靠简单 pop 保证“恰好 K 个”——相同频次的元素可能被错误截断。此时建议改用排序 + 去重后取前 K 个。

另外，C++ 中 std::vector::erase 和 unique 不会自动去重频次相同的多个不同元素，别误用。

完整函数模板要不要处理边界？

必须处理。典型边界包括：k == 0、k > freq_map.size()、输入数组为空。

建议返回 std::vector<int></int>，并在开头加检查：

if (k == 0 || nums.empty()) return {};
auto n = static_cast<int>(nums.size());
k = std::min(k, static_cast<int>(freq_map.size())); // 防止 k 超出不同元素个数
</int></int>

还有个易忽略点：std::unordered_map 插入时用 map[num]++ 是安全的，但若用 map.at(num)++ 会在 key 不存在时报 std::out_of_range 异常。

最后提醒：如果数组元素范围已知且紧凑（比如全是 0~1000 的整数），用 vector 计数比 hash map 更快更省内存，但通用解法优先选 unordered_map。