企业网站 html5黑河网站建设公司

题目：给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

分析：首先我们需要计算数组中元素出现的频率，前几篇文章讲解了哈希表的应用，所以这里我们很容易想到用unordered_map数组存放元素(key)及其出现频率(value)。然后我们需要根据value值进行排序，map的常用排序是根据key值进行的排序。所以我们根据value进行排序，需要将map转换为vector结构，然后对整个数组进行排序。但是如果我们采用优先级队列可以只维护k个有序的序列。

然后我们要考虑使用大顶堆还是小顶堆。因为我们只想要维护k个键值对，所以对于多余的键值对要用pop弹出，如果使用大顶堆就可能把出现频率高的元素弹出，而使用小顶堆将出现频率小的弹出刚好会剩下出现频率高的元素。最后由于小顶堆小的在前，所以在放入vector<int> result数组时要逆序放。

注：优先级队列如果不指定第三个参数，默认是大顶堆，所以我们可以采用仿函数（函数对象）来实现小顶堆定义。
具体代码：

class Solution {
public:class Mycomparison {public:bool operator() (const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> map;for(int i = 0; i < nums.size(); i++) {map[nums[i]]++;}priority_queue<pair<int, int>, vector<pair<int, int>>, Mycomparison> pri_que;for(unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if(pri_que.size() > k) {pri_que.pop();}}vector<int> result(k);for(int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};