排序算法、堆排序、大顶堆、小顶堆、手写快排-215. 数组中的第K个最大元素、2336. 无限集中的最小数字

目录

215. 数组中的第K个最大元素

题目链接及描述

题目分析

堆排序分析

堆排序代码编写

快排分析

快排代码编写

2336、无限集中的最小数字

题目链接及描述

题目分析

代码编写


215. 数组中的第K个最大元素

题目链接及描述

215. 数组中的第K个最大元素 - 力扣(LeetCode)

题目分析

堆排序分析

        题目所述为找到第K个最大元素,首先想到使用Arrays.sort(nums); return nums[nums.length - k]即可解决,此时很好,可以回家等通知了。

        第K个最大元素,如果创建一个小顶堆,堆顶元素为最小,并维护堆中元素个数为K,当nums数组遍历结束后,堆顶元素即为返回的元素。

        在Java中创建小顶堆以及大顶堆可以使用线程的PrioriityQueue来实现:

        Java中的单列集合Collection及其实现类如上,通过上面图示,可以看到PriorityQueue就是Collection的一个实现类,创建代码参考如下:

        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->a - b);    //小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b - a);    //大顶堆

堆排序代码编写

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->a - b);
        for(int num : nums){
            if(pq.size() < k){
                pq.add(num);
            }else if(num > pq.peek()){
                pq.poll();
                pq.add(num);
            }
        }
        return pq.peek();
    }

        这道题目如果在面试中出现的话,可能还是需要手写堆排序的,自己抽时间学习学习手写堆排序随后补充上。 

快排分析

        快排本质上就是对Arrays.sort(nums)的一种优化手段,具体可以网上查找资源,贴出自己编写的快排代码实现。

快排代码编写

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        // 第1大的元素:len - 1;
        // 第2大的元素:len - 2;
        // 第k大的元素:len - k;
        mySort(nums, 0, len - 1);
        return nums[len - k];
    }
    public void mySort(int[] nums, int L, int R){
        if(L >= R)  return;
        int pivot = nums[L];
        int le = L + 1, ge = R;
        while(true){
            while(le <= ge && nums[le] < pivot) ++le;
            while(le <= ge && nums[ge] > pivot) --ge;
            if(le >= ge)    break;
            mySwap(nums, le, ge);
            ++le;
            --ge; 
        }
        mySwap(nums, L, ge);
        mySort(nums, L, ge - 1);
        mySort(nums, ge + 1, R);
    }
    public void mySwap(int[] nums, int idx1, int idx2){
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp;
    }
}

2336、无限集中的最小数字

题目链接及描述

2336. 无限集中的最小数字 - 力扣(LeetCode)

题目分析

         初次看到这个题目并没有将其和优先级队列联系起来,题目所述首先存储了所有正整数,随后popSmallest()和addBack()两个方法,对初始化的正整数数组进行操作。

  • int popSmallest() 移除 并返回该无限集中的最小整数。
  • void addBack(int num) 如果正整数 num  存在于无限集中,则将一个 num 添加 到该无限集最后。

        首先不可能创建一个数组或者List集合将所有正整数存储起来,想到的是设置一个标志位:如threshold,此值代表的含义为【threshold, +oo)这部分正整数尚未操作过,仍然存在于初始化数组中。【1,threshold)这部分数据已经从初始化数组中弹出。

         此时对于addBack(int num)方法调用而言,只需要判断,num 和 threshold的关系,

  • 如果num >  threshold,说明原集合中已经存在num,无法继续添加。
  • 如果num <  threshold,说明除初始集合中已经不存在num,需要将其添加至集合中,由于初始使用一个值threshold代表集合,此时可以创建一个小顶堆和哈希表set用于存储num,只有set中不存在num时将num对应的数据分别添加到set和小顶堆中。【哈希表set只是判断元素num知否已经出现过,如果出现过,则不添加,否则添加】

      int popSmallest() 移除元素的方法调用此时也分为两种情况即可。

  • 如果小顶堆队列不为空,则获取小顶堆堆顶对应的元素,并将其弹出。将set中对应的元素remove()掉,返回堆顶元素即可。
  • 如果小顶堆此时为空,直接返回threshold++。即返回了当前对应的元素,同时又将当前对应元素从"集合"中删除。

代码编写

class SmallestInfiniteSet {
    public int threshold;
    public PriorityQueue<Integer> pq;
    public Set<Integer> set;
    public SmallestInfiniteSet() {
        this.threshold = 1;
        this.pq = new PriorityQueue<>((a, b)->a - b);
        this.set = new HashSet<>();
    }
    
    public int popSmallest() {
        if(pq.size() > 0){
            set.remove(pq.peek());
            return pq.poll();
        }
        return threshold++;
    }
    
    public void addBack(int num) {
        if(num >= threshold){
            return;
        }
        if(!set.contains(num)){
            set.add(num);
            pq.add(num);
        }
    }
}
/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
 * int param_1 = obj.popSmallest();
 * obj.addBack(num);
 */

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/720412.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

高压防触碰预警装置,工期重要还是命重要?

“说了多少遍了&#xff0c;不要在高压线下赶工期”吊车违规施工碰撞到高压线&#xff0c;导致供电线路跳闸停电事故&#xff0c;现场火花四溅及其危险&#xff0c; 高压线路被外力破坏的情况&#xff0c;违规施工、赶工期、视觉盲区导致线路外破等情况&#xff0c;想必大家也…

银行数仓项目实战(三)--使用Kettle进行增量,全量抽取

文章目录 使用Kettle进行全量抽取使用Kettle进行增量抽取 使用Kettle进行全量抽取 一般只有项目初始化的时候会使用到全量抽取&#xff0c;全量抽取的效率慢&#xff0c;抽取的数据量大。 我们在第一次进行全量抽取的时候&#xff0c;要在表中新建一个字段记录抽取时间&#x…

QPST的使用

QPST&#xff08;Qualcomm Product Support Tool&#xff09;是一个针对高通芯片开发的传输软件。 下载软件 进行安装 安装后使用&#xff0c;QPSTConfig 可以自动抓取dump的log 使用QFile 刷机

uniapp滚动加载

uniapp实现滚动加载&#xff0c;先获取10条数据&#xff0c;滚动到底时&#xff0c;再获取10条数据&#xff0c;以此类推&#xff0c;直至没有数据为止。 使用scroll-view&#xff0c;注意一定要给一个固定高度&#xff0c;隐藏滚动条会更美观 2. 在data中定义 3. 获取数据 …

【PyQt5】一文向您详细介绍 self.setLayout() 的作用

【PyQt5】一文向您详细介绍 self.setLayout() 的作用 下滑即可查看博客内容 &#x1f308; 欢迎莅临我的个人主页 &#x1f448;这里是我静心耕耘深度学习领域、真诚分享知识与智慧的小天地&#xff01;&#x1f387; &#x1f393; 博主简介&#xff1a;985高校的普通本硕…

5G工业路由器在智慧交通车路协同应用的深度解析

随着科技的飞速发展&#xff0c;智慧交通已成为现代城市发展的重要方向。在智慧交通的众多技术中&#xff0c;5G工业路由器凭借其高速、稳定、安全等特性&#xff0c;成为车路协同应用中不可或缺的一环。本文将在本文中深度解析5G工业路由器在智慧交通车路协同应用中的重要作用…

文件操作(2)(C语言版)

文件的随机读写&#xff1a; fseek函数&#xff1a; 前面讲解了顺序读写的相关函数&#xff0c;这里介绍一些可以“指哪写哪的函数” 有三个参数&#xff1a; 1、文件的地址 2、相对于第三个参数origin偏移的位置 3、起始位置&#xff08;有三种&#xff09; 第一种&#xff…

【三】【QT开发应用】VSQT和QTCreator项目互相转化的方法,QTCreator项目转化VSQT,VSQT转化为QTCreator

VSQT和QTCreator项目互相转化的方法 QTCreator项目转化VSQT 环境变量配置 将qmake.exe所在的目录添加到系统path里面. 转化命令 qmake -tp vc xxx.pro 生成.vcxproj文件 环境变量配置 将qmake.exe所在的目录路径添加到系统path中. 接着用cmd命令行转换,可能出现的问题 …

基于机器学习和深度学习的C-MAPSS涡扇发动机剩余寿命RUL预测(Python,Jupyter Notebook环境)

涡扇发动机全称为涡轮风扇发动机&#xff0c;是一种先进的空中引擎&#xff0c;由涡轮喷气发动机发展而来。涡扇发动机主要特点是首级压缩机的面积比涡轮喷气发动机大。同时&#xff0c;空气螺旋桨&#xff08;扇&#xff09;将部分吸入的空气从喷射引擎喷射出来&#xff0c;并…

Vue使用vue-esign实现在线签名 加入水印

Vue在线签名 一、目的二、样式三、代码1、依赖2、代码2.1 在线签名组件2.1.1 基础的2.1.2 携带时间水印的 2.2父组件 一、目的 又来了一个问题&#xff0c;直接让我在线签名&#xff08;还不能存储base64&#xff09;&#xff0c;并且还得上传&#xff0c;我直接***违禁词。 好…

基于Python的垃圾分类检测识别系统(Yolo4网络)【W8】

简介&#xff1a; 垃圾分类检测识别系统旨在利用深度学习和计算机视觉技术&#xff0c;实现对不同类别垃圾的自动识别和分类。应用环境包括Python编程语言、主流深度学习框架如TensorFlow或PyTorch&#xff0c;以及图像处理库OpenCV等&#xff0c;通过这些工具集成和优化模型&a…

M41T00串行实时时钟-国产兼容RS4C1339

RS4C1340是一种实时时钟&#xff08;RTC&#xff09;/日历&#xff0c;与ST M41T00引脚兼容&#xff0c;功能等效&#xff0c;包括软件时钟校准。该器件还提供VBAT引脚上的涓流充电能力、较低的计时电压和振荡器STOP标志。寄存器映射的块访问与ST设备相同。涓流充电器和标志需要…

MATLAB 二维平面绘图

x 0:0.01:2pi: 大家还记得这个是什么意思吧 就是0到2π 每次所取的数 是相差0.01进行选取的 ysin&#xff08;x&#xff09;: figure (这个意思就是建立一个幕布) plot&#xff08;x&#xff0c;y&#xff09; 这个主要是绘制当前的二维平面的图 但是大家会发现这张图里没有标…

ArcGIS arcpy代码工具——批量要素裁剪栅格影像

系列文章目录 ArcGIS arcpy代码工具——批量对MXD文件的页面布局设置修改 ArcGIS arcpy代码工具——数据驱动工具批量导出MXD文档并同步导出图片 ArcGIS arcpy代码工具——将要素属性表字段及要素截图插入word模板 ArcGIS arcpy代码工具——定制属性表字段输出表格 ArcGIS arc…

2024最新AI大模型-LLm八股合集(三)

常见的大模型 1.ChatGLM 1.1 背景 主流的预训练框架主要有三种&#xff1a; autoregressive自回归模型&#xff08;AR模型&#xff09; &#xff1a;代表作GPT。本质上是一个left-to-right的语言模型。 通常用于生成式任务 &#xff0c;在长文本生成方面取得了巨大的成功…

每日一练:攻防世界:qr-easy

本题思路与CTFSHOW: 36D杯 misc ez-qrcode思路相同 工具链接&#xff1a;补全二维码QRazyBox - QR Code Analysis and Recovery Toolkit (h3110w0r1d.com) 1.首先&#xff0c;我们需要基于上图的干净图像。 此二维码的大小为 29x29&#xff0c;版本V的大小为N N&#xff0c;…

msvcp100.dll已加载但找不到入口点的处理方法,分析比较靠谱的msvcp100.dll解决方法

用户在日常使用中有时会遇到一个错误提示&#xff1a;“已加载 msvcp100.dll&#xff0c;但找不到入口点”。这一信息不仅引发了使用上的不便&#xff0c;也对软件的稳定性产生了质疑。理解并解决该问题不仅对确保计算机正常运行至关重要&#xff0c;也对维护软件的长期稳定性和…

最新扣子(Coze)实战案例:扣子图像流的创建及使用,完全免费教程

&#x1f9d9;‍♂️ 诸位好&#xff0c;吾乃斜杠君&#xff0c;编程界之翘楚&#xff0c;代码之大师。算法如流水&#xff0c;逻辑如棋局。 &#x1f4dc; 吾之教程&#xff0c;内含诸般技术之秘诀。吾欲以此笔记&#xff0c;传授编程之道&#xff0c;助汝解技术难题。 &#…

电长推荐:手机数据管理软件,免费备份恢复擦除手机数据

在信息时代&#xff0c;手机成为我们生活中不可或缺的工具。然而&#xff0c;管理手机中的海量数据却往往令人头疼。 特别是对于苹果用户&#xff0c;数据管理并不像安卓那样直观方便。 今天为大家推荐一款强大且免费的工具——苹安手机管家&#xff0c;它将为你的数据管理带…

【windows|003】计算机硬件基础及存储单位

&#x1f341;博主简介&#xff1a; &#x1f3c5;云计算领域优质创作者 &#x1f3c5;2022年CSDN新星计划python赛道第一名 &#x1f3c5;2022年CSDN原力计划优质作者 &#x1f3c5;阿里云ACE认证高级工程师 &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&…