前k个高频元素（C++）

leetcode链接

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

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

思路：

1. 统计每个元素出现次数，我们可以使用unordered_map
2. 然后按出现频率给元素排序，可以考虑最小堆。优先队列是用堆实现的，可以使用优先队列。

代码：

class Solution {	//前K个高频元素
public:
	class mycomparison {	//升序
	public:
		bool operator()(const pair& Ihs, const pair& rhs) {
			return Ihs.second > rhs.second;
		}
	};
	vector topKFrequent(vector& nums, int k) {
		vector result(k);
		unordered_map umap;
		for (int i : nums) {
			umap[i]++;
		}
		
		//定义小顶堆
		priority_queue, vector>, mycomparison> pri_que;
		unordered_map::iterator iter;
		for (iter = umap.begin(); iter != umap.end(); ++iter) {
			pri_que.push(*iter);
			if (pri_que.size() > k) {	//保证堆里元素一直为k个
				pri_que.pop();
			}
		}

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

int main() {

	vector nums = { 1, 1, 1, 2, 2, 3 };
	int k = 2;
	Solution s;
	vector result = s.topKFrequent(nums, k);
	for (int i : result){
		cout << i << "t";
	}
	cout << endl;
	return 0;
}