关于暴力法简单说一点，我是用链表进行比较排序的，但是有一个细节要注意。
点击查看代码
struct node{
int val;
int count;
node*next;
node(int val,int count):val(val),count(count),next(nullptr){}
};
点击查看代码
class Solution {
struct node{
int val;
int count;
node*next;
node(int val,int count):val(val),count(count),next(nullptr){}
};
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
node*head=new node(0,0);
map<int,int>cnt,fin;
vector<int>v;
for(int i=0;i<nums.size();i++){
++cnt[nums[i]];
}
for(map<int,int>::iterator it=cnt.begin();it!=cnt.end();it++){
node*p=new node(it->first,it->second);
node*a=head;
while(a->next&&a->next->count>p->count){a=a->next;}
p->next=a->next;
a->next=p;
}
node*p=head->next;
while(p&&k){
v.push_back(p->val);
p=p->next;
--k;
}
return v;
}
};
关键的是接下来的优先级队列
这是基于大根堆和小根堆来实现的，插入的时候自动排序，专门可以解决前K元素这样的问题。
有几个关键的点：
1，自定义的初始化函数
2.如何利用根堆的特性解决问题。
1 自定义的初识化函数
默认形式是：std::priority_queue
相当于std::priority_queue<int, std::vector
如果需要小根堆，就std::priority_queue<int, std::vector
从less和greater可以看出它的定义是跟他实际逻辑相反的。
自己定义一个类也可以实现，priority_queue<pair<int,int>,vector<pair<int,int>>,mcompare>q;
点击查看代码
class mcompare{
public:
bool operator()(pair<int,int>&s,pair<int,int>&r){
return s.second>r.second;
}
};
还有这个vector<pair<int,int>>是优先级队列的底层容器，底层容器是实际存储元素的容器，它需要提供一些特定的操作，例如push、pop、top。
2如何利用根堆的特性解决问题。
一定是先插入元素，如果元素数大于K，再进行删除元素。
只有这样才能将插入的元素，进行根堆处理。
还有要注意的点是删除每次都是删除堆顶，因此高频元素就要用小根堆，每次把小的元素删除。
完整代码：
点击查看代码
class Solution {
public:
class mcompare{
public:
bool operator()(pair<int,int>&s,pair<int,int>&r){
return s.second>r.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
map<int,int>cnt;
vector<int>v(k);
for(int i=0;i<nums.size();i++){
++cnt[nums[i]];
}
priority_queue<pair<int,int>,vector<pair<int,int>>,mcompare>q;
for(map<int,int>::iterator it=cnt.begin();it!=cnt.end();it++){
q.push(*it);
if(q.size()>k){
q.pop();
}
}
for(int i=q.size()-1;i>=0;i--){
v[i]=q.top().first;
q.pop();
}
return v;
}
};