leetcode 347.前K个高频元素。
题目描述
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1] 说明： 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/top-k-frequent-elements
解题思路
首先解决的是数组中相同元素的计数问题，考虑到用map<int,int>的数据结构来存储，key保存的是元素，value保存的是元素出现的次数。然后就需要去就是topK的问题，一种是使用大顶堆，一种是使用优先队列(其底层实现也是用的堆的结构)，当然你也可以直接使用大顶堆来完成。本文是采用，优先队列来实现的。
问题
当遇到topK中元素出现次数相同比如为m次，就会出现一个结果输出m次的问题.怎么解决这个问题呢，就是在没每遍历一次map的时候，就将对应的key从map中删除。
代码实现
vector
<int> topKFrequent(vector
<int>& nums
, int k
) {
vector
<int> ans
;
if(nums
.size()==0)
return ans
;
map
<int,int> m
;
for(int i
=0;i
<nums
.size();i
++){
m
[nums
[i
]]++;
}
priority_queue
<int> pq
;
for(auto a
: m
){
pq
.push(a
.second
);
}
while(k
>0){
int a
= pq
.top();
pq
.pop();
for(auto b
:m
){
if(a
== b
.second
){
ans
.push_back(b
.first
);
m
.erase(b
.first
);
break;
}
}
k
--;
}
return ans
;
}
总结
第一次来尝试写一下自己的编程思路，其实自己也是个小白，以此来记录自己的成长过程，也希望能为大家带来一点点的收获也好，有什么不对的地方，请各位大佬指导。继续努力吧，不知道会坚持多久。
