当前位置: 首页 > news >正文

算法通关村十四关:白银挑战-堆能高效解决的经典问题

白银挑战-堆能高效解决的经典问题

1.在数组中找第K大的元素

LeetCode215
https://leetcode.cn/problems/kth-largest-element-in-an-array/

思路分析

主要解决方法有3个,选择法,堆查找法和快速排序法

方法1:选择法
先遍历一遍找到最大的元素,再遍历一遍找第二大的,依次直到第K次就找到了目标值了

方法2:堆排序法
用大堆和小堆都可以,推荐"找最大用小堆,找最小用大堆,找中间用两个堆"

构造一个大小只有k的小根堆
堆满了之后,对于小根堆,并不一定所有新来的元素都可以入堆的,只有大于根元素的才可以插入到堆中,否则直接抛弃
完成之后此时根元素恰好时当前序列下第K大的元素

代码实现:
代码自己实现起来比较困难,可以使用jdk的优先队列来解决

  • 维护一个有k个元素的最小堆
  • 如果当前堆不满,直接添加
  • 堆满的时候,如果新读到的数小于堆顶,不操作;如果大于堆顶,将堆顶拿出,然后放入新读到的数,进而让堆自己调整内部结构

方法3:快速排序法
之前已经分析过了,见前面内容

代码实现

import java.util.PriorityQueue;class Solution {public int findKthLargest(int[] nums, int k) {if(k>nums.length){return -1;}int len = nums.length;// 使用一个含有k个元素的最小堆PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a-b);for (int i = 0; i<k; i++){minHeap.add(nums[i]);}for(int i=k; i<len; i++){// 看一眼,不拿出,因为有可能没有必要替换Integer topEle = minHeap.peek();// 只要当前遍历的元素比堆顶元素大,堆顶弹出,遍历的元素进去if (nums[i] > topEle){minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.peek();}
}

python中没有现成的二叉堆,要自己实现部分功能
参考:https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/1507044/by-flix-amc8/

2.堆排序原理

排序:升序用小,降序用大

大顶推:
根结点是整个结构最大的元素
将根结点拿走,剩下的重排,此时根结点就是第二大的元素
再拿走根结点,再排
以此类推,最后堆中只剩最后一个元素,此时拿走的数据也就排好序了

拿走重排的具体过程:移除堆顶元素,把下标为n的元素放到堆顶,再通过堆化的方法,将剩下的n-1个元素重新构建成堆

小顶堆与大顶堆类似

3.合并k个排序链表

LeetCode23. 合并 K 个升序链表
https://leetcode.cn/problems/merge-k-sorted-lists/

思路分析
问题有很多种方法,现在看使用堆排序如何解决

因为每个队列都是从小到大排序的,每次都要找最小的元素,所以用小根堆;
堆的大小定义,给了几个链表,堆就定义多大;
每次都将剩余节点的最小值加到输出链表尾部,然后进行堆调整;
最后堆空的时候,合并也就完成了。

代码实现

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {if (lists == null || lists.length == 0){return null;}PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparing(node -> node.val));for (int i = 0; i<lists.length; i++){if(lists[i] != null){q.add(lists[i]);}}ListNode dummy = new ListNode(0);ListNode tail = dummy;while(!q.isEmpty()){tail.next = q.poll();tail = tail.next;if(tail.next != null){q.add(tail.next);}}return dummy.next;}
}

相关文章:

算法通关村十四关:白银挑战-堆能高效解决的经典问题

白银挑战-堆能高效解决的经典问题 1.在数组中找第K大的元素 LeetCode215 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 思路分析 主要解决方法有3个&#xff0c;选择法&#xff0c;堆查找法和快速排序法 方法1&#xff1a;选择法 先遍历一遍找到最大的…...

跨站请求伪造(CSRF)攻击与防御原理

跨站请求伪造&#xff08;CSRF&#xff09; 1.1 CSRF原理 1.1.1 基本概念 跨站请求伪造&#xff08;Cross Site Request Forgery&#xff0c;CSRF&#xff09;是一种攻击&#xff0c;它强制浏览器客户端用户在当前对其进行身份验证后的Web 应用程序上执行非本意操作的攻击&a…...

从0到1实现播放控制器

这系列文章主要讲诉如何从0到1使用QT实现带时间显示、滚动字幕等的自定义配置视频播放控制器。平时我们乘坐地铁经常看到各条线的播放控制器都大同小异。其实都是通过QT等界面开发软件来实现的。 在具体开发之前&#xff0c;需要明确我们需要做什么&#xff1f; 1. 开发一个可…...

【Vue-Element-Admin】导出el-table全部数据

背景 因为el-table实现了分页查询&#xff0c;所以想要实现el-table需要重新编写一个查询全部数据的方法 查询全部数据 listQuery: export default{return{listQuery:{//page:1,//limit:20,//如果想兼容按条件导出&#xff0c;可以定义查询条件age:undefined,sex:undefined…...

MFC 更改控件的大小和位置

获取当前主窗体的位置rect CRect dlgNow;GetWindowRect(&dlgNow);获取某一个控件当前的位置 CRect rect;CButton* pBtn (CButton*)GetDlgItem(IDC_BUTTONXXX);//获取按钮控件pBtn->GetWindowRect(rect);CWnd* pWnd(CWnd*)GetDlgItem(IDC_EDITXXX);//其它控件&#xff0…...

【向量数据库】相似向量检索Faiss数据库的安装及余弦相似度计算(C++)

目录 简介安装方法安装OpenBLAS安装lapack编译Faiss 代码示例余弦相似度计算输出ID号而非索引的改进版 简介 Faiss 是一个强大的向量相似度搜索库&#xff0c;具有以下优点&#xff1a; 高效的搜索性能&#xff1a;Faiss 在处理大规模向量数据时表现出色。它利用了高度优化的索…...

教育培训小程序的设计与功能解析

随着互联网的发展&#xff0c;线上教育逐渐成为一种趋势&#xff0c;越来越多的人开始选择在线学习。而搭建一个适合自己的线上教育小程序&#xff0c;可以为教育机构或个人提供更好的教学和学习体验。在本文中&#xff0c;我们将介绍如何通过一个第三方制作平台来搭建在线教育…...

【ES】illegal_argument_exception“,“reason“:“Result window is too large

查询ES数据返回错误&#xff1a; {"root_cause":[{"type":"illegal_argument_exception","reason":"Result window is too large, from size must be less than or equal to: [10000] but was [999999]. See the scroll api for…...

SpringBoot实现登录拦截

如果我们不进行登录拦截的话&#xff0c;即使我们跳过登录页面直接去访问任意一个页面也能访问成功&#xff0c;那么登录功能就没有意义&#xff0c;同时也会存在安全问题&#xff0c;因为有些操作是要用户登录后才能执行的&#xff0c;如果用户没有登录&#xff0c;该接口就获…...

浅谈泛在电力物联网、能源互联网与虚拟电厂

导读&#xff1a;从能源互联网推进受阻&#xff0c;到泛在电力物联网名噪一时&#xff0c;到虚拟电厂再次走向火爆&#xff0c;能源领域亟需更进一步的数智化发展。如今&#xff0c;随着新型电力系统建设推进&#xff0c;虚拟电厂有望迎来快速发展。除了国网和南网公司下属的电…...

深度学习框架安装与配置指南:PyTorch和TensorFlow详细教程

如何安装和配置深度学习框架PyTorch和TensorFlow 为什么选择PyTorch和TensorFlow&#xff1f;PyTorchTensorFlow安装PyTorch 步骤1&#xff1a;安装Python步骤2&#xff1a;使用pip安装PyTorch 安装TensorFlow 步骤1&#xff1a;安装Python步骤2&#xff1a;使用pip安装TensorF…...

vue中属性执行顺序

vue中属性的执行顺序 在Vue 2中&#xff0c;组件的生命周期和数据绑定的执行顺序如下&#xff1a; data&#xff1a;首先&#xff0c;组件会调用 data 函数&#xff0c;该函数返回一个对象&#xff0c;该对象的属性和方法会被分配给组件的 $data。init&#xff1a;接下来&…...

【代码随想录】Day 50 动态规划11 (买卖股票Ⅲ、Ⅳ)

买卖股票Ⅲ https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/ 无语了。。。 写的很好就是怎么都过不了。。。 还是就用代码随想录的写法吧。。。 class Solution { public:int maxProfit(vector<int>& prices) {int n prices.size();vector&…...

PHP反序列化漏洞

一、序列化&#xff0c;反序列化 序列化&#xff1a;将php对象压缩并按照一定格式转换成字符串过程反序列化&#xff1a;从字符串转换回php对象的过程目的&#xff1a;为了方便php对象的传输和存储 seriallize() 传入参数为php对象&#xff0c;序列化成字符串 unseriali…...

容器编排学习(一)k8s集群管理

一 Kubernetes 1 概述 就在Docker容器技术被炒得热火朝天之时&#xff0c;大家发现&#xff0c;如果想要将Docker应用于具体的业务实现&#xff0c;是存在困难的一一编排、管理和调度等各个方面&#xff0c;都不容易。于是&#xff0c;人们迫切需要一套管理系统&#xff0…...

js去除字符串空格的几种方式

方法1&#xff1a;(最常用)全部去除掉空格 var str abc d e f g ; function trim(str) { var reg /[\t\r\f\n\s]*/g; if (typeof str string) { var trimStr str.replace(reg,); } console.lo…...

Spring 自带工具——URI 工具UriComponentsBuilder

UriComponentsBuilder 是 Spring Framework 提供的一个实用工具类&#xff0c;用于构建 URI&#xff08;Uniform Resource Identifier&#xff09;。URI 是用于标识和定位资源的字符串&#xff0c;例如 URL&#xff08;Uniform Resource Locator&#xff09;就是一种特殊的 URI…...

优化案例5:视图目标列改写优化

优化案例5&#xff1a;视图目标列改写优化 1. 问题描述2. 分析过程2.1 目标SQL2.2 解决思路1&#xff09;效率低的执行计划2&#xff09;视图过滤性3&#xff09;查看已有索引定义 2.3 视图改写2.4 增添复合索引 3. 优化总结 DM技术交流QQ群&#xff1a;940124259 1. 问题描述…...

Origin绘制彩色光谱图

成果图 1、双击线条打开如下窗口 2、选择“图案”-》颜色-》按点-》映射-》Wavelength 3、选择颜色映射 4、单击填充-》选择加载调色板-》Rainbow-》确定 5、单击级别&#xff0c;设置成从370到780&#xff0c;右侧增量选择2&#xff08;越小&#xff0c;颜色渐变越细腻&am…...

项目复盘:从实践中学习

引言 在我们的工作生涯中&#xff0c;每一个项目都是一次学习的机会。项目复盘是对已完成项目的全面评估&#xff0c;旨在理解我们做得好的地方&#xff0c;以及需要改进的地方。这篇文章将分享我们如何进行项目复盘&#xff0c;以及我们从中学到了什么。 项目背景 在我们开…...

coze-loop效果展示:看AI如何将冗长代码重构为高效简洁版本

coze-loop效果展示&#xff1a;看AI如何将冗长代码重构为高效简洁版本 1. 引言&#xff1a;AI代码优化的革命性工具 在软件开发领域&#xff0c;代码优化一直是一项既重要又具有挑战性的任务。传统的优化过程往往需要开发者具备深厚的算法知识和丰富的经验积累。而今天&#…...

高效掌控暗影精灵设备:开源工具OmenSuperHub的四大突破

高效掌控暗影精灵设备&#xff1a;开源工具OmenSuperHub的四大突破 【免费下载链接】OmenSuperHub 项目地址: https://gitcode.com/gh_mirrors/om/OmenSuperHub 告别原厂软件臃肿困扰&#xff0c;体验纯净硬件控制新方式 OmenSuperHub是一款专为惠普暗影精灵笔记本打造…...

FastAdmin二次开发指南:如何基于这套开源CMS源码定制你的专属内容模型?

FastAdmin二次开发实战&#xff1a;从零构建自定义内容模型 在开源CMS领域&#xff0c;FastAdmin以其基于ThinkPHP的优雅架构和丰富的功能模块&#xff0c;成为众多开发者快速构建后台管理系统的首选。但真正体现其价值的&#xff0c;往往是在面对个性化业务需求时的二次开发能…...

数据集成工具深度评测:SeaTunnel 与 DataX、Sqoop、Flume、Flink CDC 在实时场景下的性能较量

1. 实时数据集成工具选型的关键指标 在数据驱动的时代&#xff0c;企业每天需要处理海量实时数据流。选择合适的数据集成工具直接影响业务系统的响应速度和决策效率。我经历过多次数据同步工具选型的痛苦过程&#xff0c;总结出实时场景下最关键的5个评估维度&#xff1a; 首先…...

DexGraspNet与多指手抓取算法详解:从理论到工程实现

目录 DexGraspNet与多指手抓取算法详解:从理论到工程实现 第一部分:原理详解 第一章 绪论与灵巧抓取的挑战 1.1 机器人抓取技术演进 1.1.1 从平行夹爪到多指灵巧手 1.1.2 灵巧抓取的独特挑战 1.2 DexGraspNet的研究背景与意义 1.2.1 大规模数据驱动的必要性 1.2.2 D…...

逆向视角看iOS加固:从机器码到伪代码,手把手教你分析加固效果与潜在风险

逆向视角看iOS加固&#xff1a;从机器码到伪代码的深度解析 当你在App Store下载一个应用时&#xff0c;可能不会想到这个看似简单的IPA文件背后隐藏着怎样的技术博弈。作为iOS开发者或安全研究员&#xff0c;我们常常需要从另一个角度思考——不是如何保护自己的应用&#xf…...

大语言模型,视觉模型,全模态模型,语音模型和向量模型的区别和使用

1. 大语言模型&#xff08;Large Language Model, LLM&#xff09;定义&#xff1a;以文本为输入&#xff0c;生成文本的模型。特点&#xff1a;输入输出都是自然语言&#xff08;或包含少量结构化的 prompt&#xff09;。擅长对话、写作、推理、代码生成等任务。在 LangChain …...

企业级邮件系统自建指南:从技术选型到生产部署

企业级邮件系统自建指南&#xff1a;从技术选型到生产部署 【免费下载链接】james-project James Project是一个用于电子邮件服务器的开源软件。适用于需要为其邮件基础设施提供强大和可靠的邮件传输代理的企业和组织。具有可扩展性、灵活性和易于使用的特点。 项目地址: htt…...

企业级二进制差异算法:bsdiff/bspatch的高效智能更新方案

企业级二进制差异算法&#xff1a;bsdiff/bspatch的高效智能更新方案 【免费下载链接】bsdiff bsdiff and bspatch are libraries for building and applying patches to binary files. 项目地址: https://gitcode.com/gh_mirrors/bs/bsdiff 在软件分发和持续部署领域&a…...

从Tcl脚本到实战:用Innovus自动化完成数字IC后端设计的5个高效技巧

从Tcl脚本到实战&#xff1a;用Innovus自动化完成数字IC后端设计的5个高效技巧 在数字IC后端设计领域&#xff0c;效率提升往往意味着项目周期的缩短和设计质量的提高。对于已经掌握Innovus基础操作的中级工程师而言&#xff0c;如何从手动点击界面过渡到自动化脚本驱动的工作流…...