leetcode347 前k个高频元素
题目描述
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
来源：力扣（LeetCode）
链接：LeetCode 347.前K个高频元素.
解法
对于这个问题的完成，需要用到桶排序，而C++中STL提供了完美的容器-map，它是一个关联容器，内部采用的是hash表结构，拥有快速检索的功能。
unordered_map介绍参考链接：[unordered_map详细介绍]
结果截图
图片:
代码
// 桶排序频率
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
// 键值对容器
// 在这道题中，key对应元素，value对应其出现的次数
unordered_map<int, int> counts;
int max_count = 0;
// 统计出现频次的最高
for (const int & num : nums) {
max_count = max(max_count, ++counts[num]);
}
// 根据最高频次创建所需的容器容量
// p.first对应key，p.second对应value
vector<vector<int>> buckets(max_count + 1);
// 每个频次都有一个桶，桶里装的出现了这个频次的元素
for (const auto & p : counts) {
buckets[p.second].push_back(p.first);
}
vector<int> ans;
for (int i = max_count; i >= 0 && ans.size() < k; --i) {
// 从最高频次的桶开始查询，将其输入到结果容器里，当结果容器的容量达到要求结束循环
for (const int & num : buckets[i]) {
ans.push_back(num);
if (ans.size() == k) {
break;
}
}
}
return ans;
}
};
有关题目
LeetCode 451.根据字符出现频率排序：点这里
总结
从这道题中学习了STL中map容器的一些用法。
PS: 这也是我第一篇****文章，如有不足还请大家指出，orz！