算法通关村十四关:白银挑战-堆能高效解决的经典问题
白银挑战-堆能高效解决的经典问题
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个,选择法,堆查找法和快速排序法 方法1:选择法 先遍历一遍找到最大的…...
跨站请求伪造(CSRF)攻击与防御原理
跨站请求伪造(CSRF) 1.1 CSRF原理 1.1.1 基本概念 跨站请求伪造(Cross Site Request Forgery,CSRF)是一种攻击,它强制浏览器客户端用户在当前对其进行身份验证后的Web 应用程序上执行非本意操作的攻击&a…...
从0到1实现播放控制器
这系列文章主要讲诉如何从0到1使用QT实现带时间显示、滚动字幕等的自定义配置视频播放控制器。平时我们乘坐地铁经常看到各条线的播放控制器都大同小异。其实都是通过QT等界面开发软件来实现的。 在具体开发之前,需要明确我们需要做什么? 1. 开发一个可…...
【Vue-Element-Admin】导出el-table全部数据
背景 因为el-table实现了分页查询,所以想要实现el-table需要重新编写一个查询全部数据的方法 查询全部数据 listQuery: export default{return{listQuery:{//page:1,//limit:20,//如果想兼容按条件导出,可以定义查询条件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);//其它控件࿰…...
【向量数据库】相似向量检索Faiss数据库的安装及余弦相似度计算(C++)
目录 简介安装方法安装OpenBLAS安装lapack编译Faiss 代码示例余弦相似度计算输出ID号而非索引的改进版 简介 Faiss 是一个强大的向量相似度搜索库,具有以下优点: 高效的搜索性能:Faiss 在处理大规模向量数据时表现出色。它利用了高度优化的索…...
教育培训小程序的设计与功能解析
随着互联网的发展,线上教育逐渐成为一种趋势,越来越多的人开始选择在线学习。而搭建一个适合自己的线上教育小程序,可以为教育机构或个人提供更好的教学和学习体验。在本文中,我们将介绍如何通过一个第三方制作平台来搭建在线教育…...
【ES】illegal_argument_exception“,“reason“:“Result window is too large
查询ES数据返回错误: {"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实现登录拦截
如果我们不进行登录拦截的话,即使我们跳过登录页面直接去访问任意一个页面也能访问成功,那么登录功能就没有意义,同时也会存在安全问题,因为有些操作是要用户登录后才能执行的,如果用户没有登录,该接口就获…...
浅谈泛在电力物联网、能源互联网与虚拟电厂
导读:从能源互联网推进受阻,到泛在电力物联网名噪一时,到虚拟电厂再次走向火爆,能源领域亟需更进一步的数智化发展。如今,随着新型电力系统建设推进,虚拟电厂有望迎来快速发展。除了国网和南网公司下属的电…...
深度学习框架安装与配置指南:PyTorch和TensorFlow详细教程
如何安装和配置深度学习框架PyTorch和TensorFlow 为什么选择PyTorch和TensorFlow?PyTorchTensorFlow安装PyTorch 步骤1:安装Python步骤2:使用pip安装PyTorch 安装TensorFlow 步骤1:安装Python步骤2:使用pip安装TensorF…...
vue中属性执行顺序
vue中属性的执行顺序 在Vue 2中,组件的生命周期和数据绑定的执行顺序如下: data:首先,组件会调用 data 函数,该函数返回一个对象,该对象的属性和方法会被分配给组件的 $data。init:接下来&…...
【代码随想录】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反序列化漏洞
一、序列化,反序列化 序列化:将php对象压缩并按照一定格式转换成字符串过程反序列化:从字符串转换回php对象的过程目的:为了方便php对象的传输和存储 seriallize() 传入参数为php对象,序列化成字符串 unseriali…...
容器编排学习(一)k8s集群管理
一 Kubernetes 1 概述 就在Docker容器技术被炒得热火朝天之时,大家发现,如果想要将Docker应用于具体的业务实现,是存在困难的一一编排、管理和调度等各个方面,都不容易。于是,人们迫切需要一套管理系统࿰…...
js去除字符串空格的几种方式
方法1:(最常用)全部去除掉空格 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 提供的一个实用工具类,用于构建 URI(Uniform Resource Identifier)。URI 是用于标识和定位资源的字符串,例如 URL(Uniform Resource Locator)就是一种特殊的 URI…...
优化案例5:视图目标列改写优化
优化案例5:视图目标列改写优化 1. 问题描述2. 分析过程2.1 目标SQL2.2 解决思路1)效率低的执行计划2)视图过滤性3)查看已有索引定义 2.3 视图改写2.4 增添复合索引 3. 优化总结 DM技术交流QQ群:940124259 1. 问题描述…...
Origin绘制彩色光谱图
成果图 1、双击线条打开如下窗口 2、选择“图案”-》颜色-》按点-》映射-》Wavelength 3、选择颜色映射 4、单击填充-》选择加载调色板-》Rainbow-》确定 5、单击级别,设置成从370到780,右侧增量选择2(越小,颜色渐变越细腻&am…...
项目复盘:从实践中学习
引言 在我们的工作生涯中,每一个项目都是一次学习的机会。项目复盘是对已完成项目的全面评估,旨在理解我们做得好的地方,以及需要改进的地方。这篇文章将分享我们如何进行项目复盘,以及我们从中学到了什么。 项目背景 在我们开…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
