力扣347：前K个高频元素

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

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

题解：

一、思路：

1.我希望将nums中的元素按照它们的出现次数从大到小排序。这样输出排序后的前K个元素就好；

2.如何得知nums中每个元素出现的次数呢？使用map哈希表。unordered_map<int,int>，key为nums中的元素，value为该元素出现的次数；

3.如何排序呢？考虑使用顶堆。大顶堆还是小顶堆呢？应该使用小顶堆。小顶堆中只维护K个元素，当新来的元素比队尾的元素还大时，弹出队头的元素，在队尾放入新的元素；

4.最后输出小顶堆中所有的key。

二、代码实现：

1.创建哈希表：

unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;
}

说明：map[nums[i]]++这句会执行将key为nums[i]的value进行++操作。如果没有nums[i]的key，则会先创建一个<nums[i],0>，再对value进行++操作；

2.创建小顶堆：

priority_queue<pair<int, int>, vector<pair<int, int>>, mycompare> 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();
}

说明：

(1)

priority_queue<pair<int, int>, vector<pair<int, int>>, mycompare> pri_que;

以上代码中：pair<int,int>为pri_que中的数据类型；vector<pair<int,int>>为pri_que的底层数据结构；mycompare为pri_que的比较器类。由于是小顶堆，mycompare比较器类定义如下：

class mycompare {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};

(2)

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();
}

unordered_map<int,int>::iterator it = map.begin()意味创建迭代器it作为循环变量；

3.取出顶堆中所有的元素：

vector<int>result;
for (int i = k - 1; i >= 0; i--) {result.push_back(pri_que.top().first);pri_que.pop();
}
return result;

完成代码：

class Solution {class mycompare {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};
public: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>>, mycompare> 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;for (int i = k - 1; i >= 0; i--) {result.push_back(pri_que.top().first);pri_que.pop();}return result;}
};