347. Top K Frequent Elements

时间:2022-01-21 21:18:32

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

    • 347. Top K Frequent ElementsYou may assume k is always valid, 1 ≤ k ≤ number of unique elements.
    • Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

========

题目:

因为c++中提供的哈希表map,不能按照value进行排序,

我们需要一个按照value值进行排序的数据结构,所以需要自定义一个.

定义排序函数,static bool mykeyval(const keyval &l, const keyval &r){}

利用自带的sort()函数就可以了.

====

代码

class Solution {
public:
struct keyval{
int key;//数字
int val;//数字出现的次数
keyval(int k=,int v=):key(k),val(v){}
};
static bool mykeyval(const keyval &l,const keyval &r){
return l.val>r.val;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
map<int,int> m;///key,multis
vector<int> re;
for(auto i: nums){
m[i]++;
}
vector<keyval> tmp(m.size());
int d = ;
for(auto i: m){
tmp[d].key = i.first;
tmp[d++].val = i.second;
}
sort(tmp.begin(),tmp.end(),mykeyval);
for(int i = ;i<k;i++){
re.push_back(tmp[i].key);
}
return re;
}
};