本文主要是介绍力扣第347题 前K个高频元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前言
记录一下刷题历程 力扣第347题 前K个高频元素
前K个高频元素
原题目：
分析
我们首先使用哈希表来统计数字出现的频率，然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组，对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢？假如说总共有三个数字都为1，那么我们需要把这个1放在数组下标为3的位置，假如说数组长度为n，对于这个例子就是长度为3，那么它的数组下标最大为2，不能存储在下标为3 的位置，所以我们需要创建一个长度为n+1的数组。根据我们的哈希表数字1它出现了三次那么我们把它放在数组下标为3的位置，同理数字2出现了两次我们把它放在数组下标为2的位置，最后是数字3它出现了1次所以我们把它放在数组下标为1的位置，假如说还有一个数字4他也出现了三次，那么我们将它和1共同存储在下标为3的位置，最后我们从后往前遍历数组即可。
代码如下：
class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {vector<int> res; // 用于存放结果的数组unordered_map<int, int> u_mapCount; // 用于记录每个数字的出现次数vector<vector<int>> Freq(nums.size() + 1, vector<int>()); // 用于记录频次对应的数字// 统计每个数字出现的频率for (int i = 0; i < nums.size(); i++) {u_mapCount[nums[i]] += 1;}// 将每个数字根据其频率放入对应的频率桶中for (auto& pair : u_mapCount) {Freq[pair.second].emplace_back(pair.first);}// 从高到低遍历频率桶，收集出现频率最高的数字for (int i = Freq.size() - 1; i >= 0; i--) {for (int j = 0; j < Freq[i].size(); j++) {res.emplace_back(Freq[i][j]);if (res.size() == k) { // 如果结果数组已包含k个元素，返回结果return res;}}}// 返回结果（实际不应到达这里，因为k通常会小于结果数组的大小）return res;}
};
解释注释
1.统计频率：
使用 unordered_map 记录每个数字的出现次数。这一步的时间复杂度是
n 是数组 nums 的大小。
u_mapCount 存储了每个数字及其对应的频率。
2.构建频率桶：
创建一个 vector<vector> 类型的 Freq，其中 Freq[i] 用于存储所有频率为 i 的数字。
遍历 u_mapCount，将每个数字按其频率放入相应的桶中。
3.从高到低收集频繁数字：
从 Freq 的末尾开始遍历，因为频率桶是按频率升序排列的。这样可以优先访问频率更高的数字。
遍历每个桶中的数字并将其加入结果数组 res，直到结果数组中的数字数量达到 k。
时间复杂度
这种方法利用了桶排序的思想，能够在 O(n) 的时间复杂度内完成任务，是一种高效的解决方案。
这篇关于力扣第347题 前K个高频元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
