力扣日记10.31-【栈与队列篇】前 K 个高频元素

力扣日记：【栈与队列篇】前 K 个高频元素

日期：2023.10.31
参考：代码随想录、力扣

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.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

题解

class Solution {
#define SOLUTION 2
public:vector<int> topKFrequent(vector<int>& nums, int k) {
#if SOLUTION == 1// 时间复杂度: O(n) + O(n) + O(nlogn) + O(k) = O(nlogn)// 空间复杂度: O(n+n)unordered_map<int, int> cnt;for (const auto& n: nums) {cnt[n]++;}// 将哈希表的内容复制到 vector// 使用迭代器范围构造函数（iterator range constructor）创建 sortedVector// 这个构造函数接受两个迭代器，它会遍历 cnt 中的元素，然后复制它们到 sortedVector 中vector<pair<int, int>> sortedVector(cnt.begin(), cnt.end());// 按第二个值的大小对 vector 进行排序(从大到小)sort(sortedVector.begin(), sortedVector.end(), [](const pair<int, int>& a, const pair<int, int>& b) { // 匿名函数作为比较器参数return a.second > b.second; // 前者大于后者时返回true，表示前者应该在后者前面（大在前、小在后）});// 取前k个元素int count = 0;vector<int> result;for (const auto& pair : sortedVector) {result.push_back(pair.first);count++;if (count >= k) break;}return result;}
#elif SOLUTION == 2// unordered_map + 小顶堆// O(nlogk), O(n+k)// 之所以用堆，是因为没必要对n个元素都进行排序，只需要维护前k个元素即可// 1. 首先用map遍历一遍数组，确定每个数出现的频率unordered_map<int, int> cnt;for (const auto& n: nums) {cnt[n]++;}// 2. 使用小顶堆遍历map，维护出现频率最高的前k个元素// 小顶堆：本质是一个二叉树，每个父结点的值小于子结点，即根结点的值是最小的，值从小到大排列// 关于为什么用小顶堆而不是用大顶堆：/*如果是大顶堆的话，由于其仅维护k个元素，每次push进元素时都需要pop掉根结点元素而根结点是值最大的元素，这样的话会导致最后大顶堆中都是出现频率最低的前k个元素所以要用小顶堆，每次pop元素弹出值最小的元素，维护出现频率最高的前k个元素*/// 小顶堆通过优先级队列实现priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// 用固定大小为k的小顶堆，扫面所有频率的数值for (unordered_map<int, int>::iterator it = cnt.begin(); it != cnt.end(); it++) {pri_que.push(*it); // 把it指向的<key,value>放进队列if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为kpri_que.pop();}}// 3. 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}// 小顶堆class mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second; // 为什么是>(大的在前，小的在后???)}};
#endif
};

复杂度

哈希map + 快排：
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
哈希map + 小顶堆
- 时间复杂度：O(nlogk)
- 空间复杂度：O(n)

思路总结

解法1：哈希map + 快排
- 哈希map不能直接排序，要转换为vector才能进行排序
  - 1.将哈希表的内容复制到 vector
  - 2.使用迭代器范围构造函数（iterator range constructor）创建 sortedVector
    - 这个构造函数接受两个迭代器，它会遍历 cnt 中的元素，然后复制它们到 sortedVector 中
    - vector<pair<int, int>> sortedVector(cnt.begin(), cnt.end());
  - 3.按第二个值的大小对 vector 进行排序(从大到小)
```
sort(sortedVector.begin(), sortedVector.end(), [](const pair<int, int>& a, const pair<int, int>& b) { // 匿名函数作为比较器参数return a.second > b.second; // 前者大于后者时返回true，表示前者应该在后者前面（大在前、小在后）});
```
解法2：哈希map + 小顶堆
- 之所以用小顶堆而不用快排，是因为没必要对n个元素都进行排序，只需要维护前k个元素即可（快排需要对n个元素进行排序，O(nlogn)，小顶堆每次pop和push一个元素只需要logk，即对所有元素的总时间复杂度为O(nlogk)
- 思路步骤：
- 1.首先用map遍历一遍数组，确定每个数出现的频率
- 2.使用小顶堆遍历map，维护出现频率最高的前k个元素
  - 小顶堆：本质是一个二叉树，每个父结点的值小于子结点，即根结点的值是最小的，值从小到大排列
  - 关于为什么用小顶堆而不是用大顶堆：
    如果是大顶堆的话，由于仅维护k个元素，每次push进元素时都需要pop掉根结点元素
    而根结点是值最大的元素，这样的话会导致最后大顶堆中都是出现频率最低的前k个元素
    所以要用小顶堆，每次pop元素弹出值最小的元素，维护出现频率最高的前k个元素
  - 小顶堆通过优先级队列实现：其中比较器设置为"左值>右值"（可能与优先级队列的底层实现有关）—— 注意这与快排cmp是相反的，快排cmp“左值>右值"是从大到小降序排列，而优先级队列"左值>右值"是小顶堆（根小子大）
- 3.找出前K个高频元素，因为小顶堆先弹出的是最小的（取first即元素的键），所以倒序来输出到数组
学会小顶堆的实现以及小顶堆遍历的写法：

// 小顶堆实现
class mycomparison {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};
// 优先级队列定义与遍历
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
// 参数1：优先级队列的元素类型，参数2：优先级队列自身类型，参数3：优先级队列的比较器（决定是小顶堆还是大顶堆）
for (unordered_map<int, int>::iterator it = cnt.begin(); it != cnt.end(); it++) {pri_que.push(*it); // 把it指向的<key,value>放进队列if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为kpri_que.pop();}
}