跨境网站入口,苏州网站建设n苏州网站建设公司,东至网站制作,互联网网站模块力扣日记#xff1a;【栈与队列篇】前 K 个高频元素 日期#xff1a;2023.10.31 参考#xff1a;代码随想录、力扣 347. 前 K 个高频元素
题目描述 难度#xff1a;中等 给你一个整数数组 nums 和一个整数 k #xff0c;请你返回其中出现频率前 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 105k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的
进阶你所设计算法的时间复杂度 必须 优于 O(n log n) 其中 n 是数组大小。
题解
class Solution {
#define SOLUTION 2
public:vectorint topKFrequent(vectorint nums, int k) {
#if SOLUTION 1// 时间复杂度: O(n) O(n) O(nlogn) O(k) O(nlogn)// 空间复杂度: O(nn)unordered_mapint, int cnt;for (const auto n: nums) {cnt[n];}// 将哈希表的内容复制到 vector// 使用迭代器范围构造函数iterator range constructor创建 sortedVector// 这个构造函数接受两个迭代器它会遍历 cnt 中的元素然后复制它们到 sortedVector 中vectorpairint, int sortedVector(cnt.begin(), cnt.end());// 按第二个值的大小对 vector 进行排序(从大到小)sort(sortedVector.begin(), sortedVector.end(), [](const pairint, int a, const pairint, int b) { // 匿名函数作为比较器参数return a.second b.second; // 前者大于后者时返回true表示前者应该在后者前面大在前、小在后});// 取前k个元素int count 0;vectorint 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(nk)// 之所以用堆是因为没必要对n个元素都进行排序只需要维护前k个元素即可// 1. 首先用map遍历一遍数组确定每个数出现的频率unordered_mapint, int cnt;for (const auto n: nums) {cnt[n];}// 2. 使用小顶堆遍历map维护出现频率最高的前k个元素// 小顶堆本质是一个二叉树每个父结点的值小于子结点即根结点的值是最小的值从小到大排列// 关于为什么用小顶堆而不是用大顶堆/*如果是大顶堆的话由于其仅维护k个元素每次push进元素时都需要pop掉根结点元素而根结点是值最大的元素这样的话会导致最后大顶堆中都是出现频率最低的前k个元素所以要用小顶堆每次pop元素弹出值最小的元素维护出现频率最高的前k个元素*/// 小顶堆通过优先级队列实现priority_queuepairint, int, vectorpairint, int, mycomparison pri_que;// 用固定大小为k的小顶堆扫面所有频率的数值for (unordered_mapint, 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个高频元素因为小顶堆先弹出的是最小的所以倒序来输出到数组vectorint 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 pairint, int lhs, const pairint, int rhs) {return lhs.second rhs.second; // 为什么是(大的在前小的在后???)}};
#endif
};复杂度
哈希map 快排 时间复杂度O(nlogn)空间复杂度O(n) 哈希map 小顶堆 时间复杂度O(nlogk)空间复杂度O(n)
思路总结
解法1哈希map 快排 哈希map不能直接排序要转换为vector才能进行排序 1.将哈希表的内容复制到 vector2.使用迭代器范围构造函数iterator range constructor创建 sortedVector 这个构造函数接受两个迭代器它会遍历 cnt 中的元素然后复制它们到 sortedVector 中vectorpairint, int sortedVector(cnt.begin(), cnt.end()); 3.按第二个值的大小对 vector 进行排序(从大到小) sort(sortedVector.begin(), sortedVector.end(), [](const pairint, int a, const pairint, 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 pairint, int lhs, const pairint, int rhs) {return lhs.second rhs.second;}
};
// 优先级队列定义与遍历
priority_queuepairint, int, vectorpairint, int, mycomparison pri_que;
// 参数1优先级队列的元素类型参数2优先级队列自身类型参数3优先级队列的比较器决定是小顶堆还是大顶堆
for (unordered_mapint, 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();}
}
