【leetcode100-074/075/076】【堆】三题合集

2024-01-29 06:20

本文主要是介绍【leetcode100-074/075/076】【堆】三题合集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【降序第k元素】

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路:

既然在堆专题,那我们就先用堆来解一下,用STL固然很爽,但这里还是得手撕一下,不然显得这个题很多余。。

  • 首先是建堆过程,以本题需要的大根堆为例:我们从最后一个有孩子的节点开始,检查它和孩子(们)的关系,只要孩子中有比它更大的,就用孩子中更大的那一个和它交换位置,如果发生了交换,则还要继续检查新的以它为根节点的子树是否合法。从后到前依次检查完所有节点后,一个合法的堆就建好了。
  • 然后是取出前k个数的过程,由于我们采用了vector来存储堆,所以可以通过设置下标界限来控制堆的大小,每次我们将堆顶和当前堆内的最后一个元素交换位置,并缩小下标范围,将被换到末尾去的原堆顶元素从堆内取出,并从堆顶开始调整被换上去的节点的位置,直到堆重新合法。将此过程重复k-1次,我们就取出了堆中前k-1大的数,此时留在堆顶的就是原数组中倒序第k个元素了。

不考虑专题的话,其实本题还可以用快速选择来解,也就是快排partition思想的应用。每次partition我们可以确定一个元素的正确位置,然后我们可以通过k和这个正确元素下标的关系,来确定第k大的元素在这个下标的左边部分/右边部分/就是这个数本身。反复进行partition操作直到找到指定下标即可。

//大根堆
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int n = nums.size();//建堆for (int i = n / 2 - 1; i >= 0; i--) {//调整根节点为i的树int cur = i;while (cur < n / 2) {//有孩子比parent大//只有左孩子if (2 * cur + 2 >= n) {//左孩子比parent大if (nums[2 * cur + 1] > nums[cur]) {swap(nums[cur], nums[2 * cur + 1]);cur = 2 * cur + 1;} elsebreak;}//左右孩子都有else if (nums[cur] < nums[2 * cur + 1] ||nums[cur] < nums[2 * cur + 2]) {//左孩子大if (nums[2 * cur + 1] >= nums[2 * cur + 2]) {swap(nums[cur], nums[2 * cur + 1]);cur = 2 * cur + 1;} else {swap(nums[cur], nums[2 * cur + 2]);cur = 2 * cur + 2;}} else {break;}}}//删k-1次,堆顶就是要找的//树内最大下标int limit = n;for (int i = 1; i < k; i++) {//删:换到末尾,范围--swap(nums[0], nums[limit - 1]);limit--;//从根开始调整int cur = 0;while (cur < limit / 2) {//只有左孩子if (2 * cur + 2 >= limit) {//左孩子比parent大if (nums[2 * cur + 1] > nums[cur]) {swap(nums[cur], nums[2 * cur + 1]);cur = 2 * cur + 1;} elsebreak;}//左右孩子都有else if (nums[cur] < nums[2 * cur + 1] ||nums[cur] < nums[2 * cur + 2]) {//左孩子大if (nums[2 * cur + 1] >= nums[2 * cur + 2]) {swap(nums[cur], nums[2 * cur + 1]);cur = 2 * cur + 1;} else {swap(nums[cur], nums[2 * cur + 2]);cur = 2 * cur + 2;}} else {break;}}}return nums[0];}
};

【前k高频元素】

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

思路:

本题虽然放在堆,但我感觉后面堆排序取出前k个元素的过程是一眼就能想到的思路,反而是前面统计频次并把信息转换成堆可以使用的样子比较难想,可能是因为对数据结构的熟悉程度还不太够。

  • 先来说转换部分:首先统计频次,自然是哈希表了,用一个unordered_map给它存下来。可是哈希表不能自己换顺序,怎么办?其实很简单,unordered_map里面存储的元素就是pair啊,我们用一个vector把这些pair都存起来不就好了,到了vector里面那不是你想咋换咋换呢。好了,到此我们需要的数据就准备好了。
  • 然后就是建个堆,注意比较的时候要用pair的second元素,再手动pop堆顶k次就好了(没错还是手撕,不然感觉白写这个题)。
class Solution {
public://传入下标范围void adjustHeap(vector<pair<int, int>>& elements, int cur, int limit) {//还有孩子while (2 * cur + 1 <= limit) {int lchild = 2 * cur + 1;int rchild = 2 * cur + 2;//只有左孩子if (rchild > limit) {if (elements[cur].second < elements[lchild].second) {swap(elements[cur], elements[lchild]);cur = lchild;} elsebreak;} else { //两个孩子//有至少一个比parent大if (elements[cur].second < elements[lchild].second ||elements[cur].second < elements[rchild].second) {//把更大的换上去if (elements[lchild].second >= elements[rchild].second) {swap(elements[cur], elements[lchild]);cur = lchild;} else {swap(elements[cur], elements[rchild]);cur = rchild;}} elsebreak;}}}vector<int> topKFrequent(vector<int>& nums, int k) {//哈希表统计一遍unordered_map<int, int> hash;for (int a : nums) {hash[a]++;}//存到vectorvector<pair<int, int>> elements(hash.begin(), hash.end());// 1.直接sort+输出// 2.前k个建堆+遍历剩余+输出// 3.整体建堆,输出k次int n = elements.size();for (int i = n / 2 - 1; i >= 0; i--) {adjustHeap(elements, i, n - 1);}vector<int> ans;for (int i = 0; i < k; i++) {ans.push_back(elements[0].first);swap(elements[0], elements[n - i - 1]);adjustHeap(elements, 0, n - i - 2);}return ans;}
};

【数据流中位数】

中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

  • MedianFinder() 初始化 MedianFinder 对象。

  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

思路:

一开始被hard定位给吓到了,实际上逻辑很简单,实现细节也不多,感觉甚至还不如二分查找的各种变体麻烦(可恶真的很麻烦),属于只要你知道这个思路从此以后同类型的题都可以屡试不爽的那种类型。

首先我们观察中位数的位置,不管它是一个还是两个,如果我们在第一个的右边切一刀,把一个有序数组切成两半,会发生什么?第一个数一定是左半边所有数里最大的,而如果有第二个数,它一定是右半部分最小的,以及左右两半的元素个数要么相同,要么左边比右边多一个。

有了这三条规则,该做什么就很清楚了。

初始状态我们的数组是空的,随着新数字的到来,我们依次将其按照规则添加到数组中,并实时地计算出添加后左右半边的最大值和最小值,就可以顺利地随时获取中位数啦。

那么如何实时地计算出添加后左右半边的最大值和最小值呢,显然堆很合适干这个事情。

每次拿到一个数,我们先根据当前的中位数判断它应该在左半边or右半边,并把它插入相应的堆+调整好。注意,这时候我们的第三条规则“左右两半的元素个数要么相同,要么左边比右边多一个”是有可能被破坏的,所以针对这个被破坏的情况我们还需要从造成规则破坏的那一边拿一个元素到另一边去,以恢复两边元素数量关系的合法性。这题就不手撕堆了,用priority_queue偷懒一下吧qwq。

class MedianFinder {
public:priority_queue<int, vector<int>, less<int>> left;priority_queue<int, vector<int>, greater<int>> right;MedianFinder() {}void addNum(int num) {//空if (left.empty()) {left.push(num);return;}//偶数插左边if (left.size() == right.size()) {//非空,num应该在左边if (num <= left.top()) {//左堆插入left.push(num);}//非空,num应该在右边else {//左堆插入right[0],右堆right[0]换numright.push(num);left.push(right.top());right.pop();}}//奇数插右边else {// num应该在左边if (num < left.top()) {//右堆插入left[0],左堆插入numleft.push(num);right.push(left.top());left.pop();}// num应该在右边else {//右堆插入right.push(num);}}}double findMedian() {//偶数取平均if (left.size() == right.size()) {return (left.top() + right.top()) / 2.0;}//奇数左根else {return 1.0 * left.top();}}
};

这篇关于【leetcode100-074/075/076】【堆】三题合集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/655996

相关文章

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

EasyPlayer.js网页H5 Web js播放器能力合集

最近遇到一个需求,要求做一款播放器,发现能力上跟EasyPlayer.js基本一致,满足要求: 需求 功性能 分类 需求描述 功能 预览 分屏模式 单分屏(单屏/全屏) 多分屏(2*2) 多分屏(3*3) 多分屏(4*4) 播放控制 播放(单个或全部) 暂停(暂停时展示最后一帧画面) 停止(单个或全部) 声音控制(开关/音量调节) 主辅码流切换 辅助功能 屏

C++语法知识点合集:11.模板

文章目录 一、非类型模板参数1.非类型模板参数的基本形式2.指针作为非类型模板参数3.引用作为非类型模板参数4.非类型模板参数的限制和陷阱:5.几个问题 二、模板的特化1.概念2.函数模板特化3.类模板特化(1)全特化(2)偏特化(3)类模板特化应用示例 三、模板分离编译1.概念2.模板的分离编译 模版总结 一、非类型模板参数 模板参数分类类型形参与非类型形参 非类型模板

Linux性能分析工具合集

Linux性能分析工具合集 工具合集主要包含以下各种工具,对于了解Linux系统结构、网络结构、内核层次具有一定的帮助。 Linux Performance Observability ToolsLinux Static Performance ToolsLinux Performance Benchmark ToolsLinux Performance Tuning ToolsLinux

JVM合集

序言: 1.什么是JVM? JVM就是将javac编译后的.class字节码文件翻译为操作系统能执行的机器指令翻译过程: 前端编译:生成.class文件就是前端编译后端编译:通过jvm解释(或即时编译或AOT)执行.class文件时跨平台的,jvm并不是跨平台的通过javap进行反编译 2.java文件是怎么变成.class文件的? 属于前端编译 3..class文件解读 采用1

C语言程序与设计第四版课后习题 - 1~8章大合集

前言 本文章是一个大合集,按照课后习题的命名方式命名,方便寻找,只需要在目录上点相对应的题号即可在这里插入图片描述 第一章课后习题 1.1 编写一个C程序 题目概述: 请参照本章例题,编写一个C程序,输出一下信息: *****************************Very good!***************************** 代码实现: #define

《黑神话:悟空》专题合集MOD/修改器/壁纸/音乐/CG剧情

《黑神话:悟空》专题合集」 链接:https://pan.quark.cn/s/d67857f4e308 包含内容: 《黑神话:悟空》MOD合集 《黑神话:悟空》修改器(风灵月影) 《黑神话:悟空》壁纸合集 《黑神话:悟空》3小时CG完整剧情合集 4K120帧最高画质!国语 简中字幕 附:4K 结尾动画合集 ​​​国语 简中字幕 《黑神话:悟空》主题曲 《黑神话

【鼠鼠学AI代码合集#5】线性代数

在前面的例子中,我们已经讨论了标量的概念,并展示了如何使用代码对标量进行基本的算术运算。接下来,我将进一步说明该过程,并解释每一步的实现。 标量(Scalar)的基本操作 标量是只有一个元素的数值。它可以是整数、浮点数等。通过下面的 Python 代码,我们可以很容易地进行标量的加法、乘法、除法和指数运算。 代码实现: import torch# 定义两个标量x = torch.tens

diffusion model 合集

diffusion model 整理 DDPM: 前向一步到位,从数据集里的图片加噪声,根据随机到的 t t t 决定混合的比例,反向要慢慢迭代,DDPM是用了1000步迭代。模型的输入是带噪声图和 t,t 先生成embedding后,用通道和的方式加到每一层中间去: 训练过程是对每个样本分配一个随机的t,采样一个高斯噪声 ϵ \epsilon ϵ,然后根据 t 对图片和噪声进行混合,将加噪

【新东西】链接合集

1、RxJava。 基础介绍:http://www.jianshu.com/p/5e93c9101dc5 详细介绍:http://gank.io/post/560e15be2dca930e00da1083 方法介绍:https://zhuanlan.zhihu.com/p/21926591 2、Retrofit。网络请求框架,外包代码里用的这个。 简单介绍:http://blog.csd