前 K 个高频元素(两种方法实现)

题目：

这是leetcode上的一道题，首先，我们看下题目：

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

输入: nums = [1], k = 1
输出: [1]
1
2
3
4
5
6
7
8
9

思路一：

题目的要求是，获取出现频率最高的前 k个元素，既然是前 k 个，很明显就是用堆排序的方式去实现，步骤是：
1.将前k个数，用构造成大根堆或者小根堆，因为我们是去前k个大的数，用小根堆。

2.将剩余的元素一一与堆的第一个元素比较，如果比第一个元素大则替换；
替换后的值与其左右孩子节点中的最小节点作比较，如果大于其最小孩子节点，就交换两个的元素值；
交换后的孩子节点，继续向下与其的孩子节点做比较，如果大于则交换，循环进行直到没有孩子节点或者不大于为止；
注意：：由于这里求得是频率高的元素，所以需要用哈希表记录每个元素出现的频率
实现代码如下：

#include<iostream>
#include<windows.h>
#include< vector >
#include< algorithm >
#include< unordered_map >
vector<int> topKFrequent(vector<int>& nums, int k) {
	unordered_map<int, int> mp; // {元素值， 频率}
	for (auto n : nums) {
		mp[n]++;	// 先用哈希表记录出现频率
	}
	int c = 0;
	vector<int> heap(k);
	for (auto m : mp) {
		if (c < k) {	// 用前 k 个元素构造 小根堆
			// 构造小根堆
			heap[c] = m.first;	//插入元素值
			int index = c;
			int parentIndex = (c - 1) / 2;
			while (mp[heap[index]] < mp[heap[parentIndex]]) {// 插入的是元素值，但是用频率比较
				swap(heap[index], heap[parentIndex]);	// 交换节点 与 父节点的值
				index = parentIndex;
				parentIndex = (index - 1) / 2;
			}
			c++;
			
		}
		else {
			// k + 1及以后的元素 插入小根堆
			if (m.second > mp[heap[0]]) {	// 我们去的是频率高的,所以是插入大于 堆最小元素的 值
				heap[0] = m.first;
				int index = 0;
				int leftIndex = index * 2 + 1;
				int rightIndex = index * 2 + 2;
				int curIndex;
				while (leftIndex < k) {
					if (rightIndex < k && mp[heap[rightIndex]] < mp[heap[leftIndex]]) {
						curIndex = rightIndex;
					}
					else {
						curIndex = leftIndex;
					}
					if (mp[heap[curIndex]] < mp[heap[index]]) {//子节点小于父节点，交换（维护小根堆）
						swap(heap[curIndex], heap[index]);	//交换节点和最小子节点的值
						index = curIndex;
						leftIndex = index * 2 + 1;
						rightIndex = index * 2 + 2;
					}
					else {
						break;
					}

				}
			}
		}
	}
	return heap;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

这种方法是比较优秀的方法，时间复杂度是 O(nlogk)
下面来一种简单粗暴的方法：

思路二：

利用优先队列的自动排序特性,每次插入只需将末尾的元素移除即可，非常简单粗暴.
实现代码是：

#include<iostream>
#include<windows.h>
#include< vector >
#include< algorithm >
#include< unordered_map >
#include< queue >
vector<int> topKFrequent(vector<int>& nums, int k) {
	unordered_map<int, int> mp;
	for (auto n : nums) {
		mp[n]++;
	}
	priority_queue<pair<int, int>>pq;	// 声明优先级队列
	for (auto m : mp) {
		pq.push({ -m.second, m.first });//将元素入栈，自动按升序排序，频率取负数，则频率高的排前面
		if (pq.size() > k) {
			pq.pop();	// 插入元素后会自动排序，只需将最后一位出队即可
		}
	}
	vector<int> res;
	while (k--) {
		res.emplace_back(pq.top().second);	// 循环获取所有元素
		pq.pop();
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度也是O(nlogk),但是需要频繁的入队出队，性能反而比不上手写的堆排序（思路一）

总结：

如果手写堆排序虽然看着比较麻烦，但是由于比较细致，性能反而会比较好，毕竟是具体问题具体分析。而用优先队列，则是使用了标准库的强大功能，但是由于题目要求，并不是最优解。