mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
103 lines
4.5 KiB
Markdown
103 lines
4.5 KiB
Markdown
# [347. Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/)
|
||
|
||
# 思路
|
||
|
||
要求数组里面出现频次最高的k个数。如果我们遍历一遍数组把每个数频次都用hash记录下来，那这题就和和[215. 数组中第k大的数](https://leetcode.com/problems/kth-largest-element-in-an-array/)是差不多的，
|
||
即用快排划分或者堆的思想，请参见[215题解](https://github.com/ShusenTang/LeetCode/blob/master/solutions/215.%20Kth%20Largest%20Element%20in%20an%20Array.md)。
|
||
|
||
## 思路一、堆
|
||
|
||
这里求的是频率最高的k个数，所以我们用最小堆，从前往后先将k个频次入堆，堆size达到k后，需要判断：
|
||
* 若新来的频次比堆顶大，说明堆顶的频次应该被淘汰，并将新来的频次push进堆；
|
||
* 否则说明新来的频次不够大，那跳过即可。
|
||
|
||
注意堆的size始终是k，初始建堆复杂度O(k)，每次从堆顶删除元素和插入元素复杂度都是O(k)，有大约n次操作，所以时间复杂度为O(nlogk)；空间复杂度O(k)。
|
||
|
||
几个注意点：
|
||
* 也可以用最大堆，但是需要注意的是用最大堆要先把所有元素都加入堆，堆大小就为n，再不断pop出k个元素。由于堆大小为n级别，所以建堆复杂度为O(n)，总的时间复杂度为O(n + klogn)；空间复杂度O(n)。**当n很大时用最大堆是不好的，将耗费大量空间。**
|
||
* STL中堆用`priority_queue`实现，不过默认是最大堆，这里我们需要最小堆，需要传入`greater`类（而不是函数）。
|
||
* 代码实现中堆的元素是一个pair, 由于pair排序默认对first排序，所以first我们定义成频次，second定义成元素值。
|
||
|
||
时间复杂度O(nlogk)
|
||
|
||
## 思路二、快排划分
|
||
|
||
我们得到每个数的频次后，可以先计算出第k大的频次（记为time_k），这是可以利用快排划分的思想在平均O(n)的复杂度计算出来的。然后再判断每个数的频次是否大于等于time_k。
|
||
|
||
计算无序数组中第k大的数在STL中即`nth_element`，几个注意点：
|
||
* `nth_element`默认是从小到大排序，所以这里需要传入`greater<int>()`函数；
|
||
* `nth_element`没有返回值，它只是保证第n(从0开始)个元素是位于最终排序位置的。
|
||
|
||
时间复杂度平均为O(n)
|
||
|
||
|
||
## 思路三、桶排序
|
||
|
||
求数组中第k大的数时，如果数组的所有元素是固定范围的（有限的），那么就可以使用桶排序。
|
||
|
||
对于此题来说，频次数组中元素最大也不过于`nums.size()`，所以可以使用桶排序。
|
||
为此，我们可以开辟一个一维大小为`nums.size() + 1`的二维数组`buckets`，`buckets[i]`代表出现频次为i的所有数。代码就不给了很简单。
|
||
|
||
时间复杂度O(n)
|
||
|
||
|
||
## 思路一
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
vector<int> topKFrequent(vector<int>& nums, int k) {
|
||
unordered_map<int, int>count;
|
||
for(int & num: nums) count[num]++;
|
||
|
||
// pair<频次, num>, 因为对pair排序默认对first排序
|
||
// greater表示用最小堆(不指定的话默认最大堆)
|
||
priority_queue<pair<int, int>, vector<pair<int,int>>,
|
||
greater<pair<int, int>> >min_heap;
|
||
|
||
for(auto it = count.begin(); it != count.end(); it++){
|
||
if(min_heap.size() == k && min_heap.top().first < it->second)
|
||
min_heap.pop();
|
||
if(min_heap.size() < k)
|
||
min_heap.push({it -> second, it -> first});
|
||
|
||
// min_heap.push({it -> second, it -> first});
|
||
// if(min_heap.size() > k) min_heap.pop();
|
||
}
|
||
|
||
vector<int>res;
|
||
while(!min_heap.empty()){
|
||
res.push_back(min_heap.top().second);
|
||
min_heap.pop();
|
||
}
|
||
//reverse(res.begin(), res.end()); // 题目好像没说要正序
|
||
return res;
|
||
}
|
||
};
|
||
```
|
||
|
||
## 思路二
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
vector<int> topKFrequent(vector<int>& nums, int k) {
|
||
unordered_map<int, int>count;
|
||
for(int & num: nums) count[num]++;
|
||
|
||
vector<int>times;
|
||
for(auto it = count.begin(); it != count.end(); it++)
|
||
times.push_back(it -> second);
|
||
|
||
nth_element(times.begin(), times.begin() + k - 1, times.end(), greater<int>());
|
||
int time_k = times[k - 1];
|
||
|
||
vector<int>res;
|
||
for(auto it = count.begin(); it != count.end(); it++){
|
||
if(it -> second >= time_k)
|
||
res.push_back(it -> first);
|
||
}
|
||
|
||
return res;
|
||
}
|
||
};
|
||
```
|