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].
其实最简单的就是想到就是用一个小顶堆实现，如果堆中元素个数小于K，则插入元素，如果大于K，则和堆顶比较，如果大于堆顶，则弹出堆顶，插入新元素。
自己实现红黑树有点难，好在C++ STL容器中，map,set和priority_queue都是实现了红黑树结构的，所以可以拿来用。首先这边上一种我最开始自己实现的算法，通过排序来实现的。
1.设置一个unorderd_map<int,int>对每一个vector中的数据进行统计，统计出个数，然后将pair<int,int>放入vector中自己定义排序的比较算法，选取前K个，最后出来时间上还可以 Beate 70%+
代码也很容易理解，如下：
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> myMap;
for( int i = 0; i < nums.size(); i++ ){
myMap[nums[i]]++;
}
vector<PAIR> mapMember;
for( auto m : myMap){
mapMember.push_back(m);
}
sort( mapMember.begin(),mapMember.end(),myCMP);
vector<int> result;
for( int i = 0; i < k; i++ ){
result.push_back(mapMember[i].first);
}
return result;
}
private:
typedef pair<int,int> PAIR;
static bool myCMP (PAIR& num1, PAIR& num2){
return num1.second > num2.second;
}
};
思路2：用最小堆：首先需要了解一下C++中的优先队列priority_queue进行一个了解，priority_queue 优先级队列是一个拥有权值概念的单向队列queue，在这个队列中，所有元素是按优先级排列的（也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素优先权要高于后进入队列的元素）。他的模板声明带有三个参数，priority_queue<Type, Container, Functional>Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。第一个是元素类型，这边的话就是pair<int,int> 第二个是保存数据的容器，一般默认使用vector,第三个是比较方式，如果不定义，默认是大顶堆，这边因为需要小顶堆实现，所以使用greater<>；
代码：
typedef pair<int, int> P;
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
for (int x : nums) cnt[x] ++;
priority_queue<P, vector<P>, greater<P> > q;
for (auto &x : cnt) {
if (q.size() < k)
q.push(make_pair(x.second, x.first));
else {
if (q.top().first < x.second) {
q.pop();
q.push(make_pair(x.second, x.first));
}
}
}
vector<int> ans;
while (!q.empty()) {
ans.push_back(q.top().second);
q.pop();
}
return ans;
}
};
这边需要注意，这里pair中，first和second通过make_pair掉位置了，为什么呢？因为对于pair来说，默认的比较操作是比较first成员的，但是我们这边需要比较的second的数据，所以需要调一个位置。