算法通关村-----堆在查找和排序中的应用
数组中的第K个最大元素
问题描述
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。详见leetcode215
问题分析
可以创建一个包含k个元素的最小堆,初始时,将数组元素中的前K个放入堆中,之后,遍历数组中的其他元素,与堆顶元素比较,只有大于堆顶元素,才将该元素与堆顶元素替换(即先执行删除,在执行插入),遍历结束后,堆顶元素即是数组中第K大的元素。
代码实现
public int findKthLargest(int[] nums, int k) {if(k>nums.length){return -1;}PriorityQueue<Integer> minHeap = new PriorityQueue<>(4, (a, b) -> a - b);for(int i=0;i<k;i++){minHeap.offer(nums[i]);}for(int i=k;i<nums.length;i++){if(nums[i]>minHeap.peek()){minHeap.poll();minHeap.offer(nums[i]);}}return minHeap.poll();
}
堆排序
问题描述
给定整数数组nums,使用堆排序对数组中的元素进行排序。
问题分析
使用堆排序对数组元素进行排序
代码实现
public static void heapSort(int[] nums){PriorityQueue<Integer> minHeap = new PriorityQueue<>(nums.length,(a,b) -> a-b);for (int i = 0; i < nums.length; i++) {minHeap.offer(nums[i]);}for (int i = 0; i < nums.length; i++) {nums[i] = minHeap.poll();}
}
合并K个有序链表
问题描述
给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。详见leetcode23
问题分析
链表数组中存放的其实是每个链表的头节点,可以根据链表的长度创建相同大小的最小堆,将链表中的节点放入堆中,之后,取堆顶元素,即为最小元素,并取出元素的下一个元素放入堆中。
代码实现
public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>((a,b) -> a.val-b.val);for(int i=0;i<lists.length;i++){if(lists[i]!=null){minHeap.offer(lists[i]);}}ListNode vhead = new ListNode(-1);ListNode iter = vhead;while(!minHeap.isEmpty()){ListNode node = minHeap.poll();iter.next = node;iter = node;if(iter.next!=null){minHeap.offer(iter.next);}}return vhead.next;
}
总结
堆查找和排序的应用主要是指堆排序和查找最大最小元素,或者第几大,第几小元素的问题上。这里我们遵循的原则是:
查找:查大用小堆,查小用大堆
排序: 升序用小堆,降序用大堆
堆的操作过程比较复杂,在java中,可以使用优先队列实现堆的操作,因为java中的优先队列是基于堆实现的。
相关文章:
算法通关村-----堆在查找和排序中的应用
数组中的第K个最大元素 问题描述 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。详见le…...
直方图统计增强方法
直方图统计增强方法的原理: 直方图统计增强是一种基于像素值分布的图像增强技术,通过调整像素值的分布来增强图像的对比度和细节。其原理是根据图像的直方图信息,将原始像素值映射到一个新的像素值域,从而改变图像的亮度和对比…...

字节二面:如果高性能渲染十万条数据?
前言 最近博主在字节面试中遇到这样一个面试题,这个问题也是前端面试的高频问题,作为一名前端开发工程师,我们虽然可能很少会遇到后端返回十万条数据的情况,但是了解掌握如何处理这种情况,能让你对前端性能优化有更深的…...

Mysql高阶语句(二)
一、设置别名(alias ——>as) 在 MySQL 查询时,当表的名字比较长或者表内某些字段比较长时,为了方便书写或者 多次使用相同的表,可以给字段列或表设置别名。使用的时候直接使用别名,简洁明了࿰…...

算法笔记 二叉搜索树
二叉搜索树(Binary Search Tree,简称 BST)是一种数据结构,用于存储具有可比较键(通常是数字或字符串)的元素 1 结构特点 节点结构:每个节点都有一个键和两个子节点(左子节点和右子…...
微软牵手Linux:Ubuntu“系统”上架win10应用商店啦
导读继SUSE Linux登陆之后,Ubuntu今天正式以UWP应用的身份上架Win10应用商店。Windows Insider用户升级到Win10秋季创意者更新预览版Build 16190及以上就可以下载和安装Ubuntu系统应用。一旦下载和安装完Ubuntu应用后,它将开始在你的Windows10 PC上安装U…...
leetcode做题笔记126. 单词接龙 II
按字典 wordList 完成从单词 beginWord 到单词 endWord 转化,一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列,并满足: 每对相邻的单词之间仅有单个字母不同。转换过程中的每个单词 s…...
windows下运行springboot的jar包,修改替换class文件,修改配置文件application,打包
在windows下跑springboot的jar包,经常会用到一些命令行和操作。 1、修改配置文件(以application.yml为例) #提取文件 jar xvf mqtt-10.1.0.jar BOOT-INF/classes/application.yml#将文件装回jar包 jar uvf mqtt-10.1.0.jar BOOT-INF/classe…...
PMD 检查java代码:可以去掉无用的括号(UselessParentheses)
这个规则的优先级比较低。 https://docs.pmd-code.org/pmd-doc-6.55.0/pmd_rules_java_codestyle.html#uselessparentheses 无用的括号可以去掉。当然,有时候为了避免理解起来困难,加上括号反而更加清晰。 例如: public static short calc…...

【数据结构练习】栈的面试题集锦
目录 前言: 1.进栈过程中可以出栈的选择题 2.将递归转化为循环 3.逆波兰表达式求值 4.有效的括号 5. 栈的压入、弹出序列 6. 最小栈 前言: 数据结构想要学的好,刷题少不了,我们不仅要多刷题,还要刷好题&#x…...

简单工厂模式概述和使用
目录 一、简单工厂模式简介1. 定义2. 使用动机 二、简单工厂模式结构1.模式结构2. 时序图 三、简单工厂的使用实例四、简单工厂模式优缺点五、简单工厂模式在Java中的应用 一、简单工厂模式简介 原文链接 1. 定义 简单工厂模式(Simple Factory Pattern):又称为静…...

软件工程概述
软件工程概述 软件工程指的是应用计算机科学、数学及管理科学等原理,以工程化的原则和方法来解决软件问题的工程,目的是提高软件生产效率、提高软件质量、降低软件成本。 1. 计算机软件 计算机软件指的是计算机系统中的程序及其文档。程序是计算任务的…...

国际网页短信软件平台搭建定制接口说明|移讯云短信系统
国际网页短信软件平台搭建定制接口说明|移讯云短信系统 通道路由功能介绍 支持地区通道分流,支持关键字,关键词通道分流,支持白名单独立通道,支持全网通道分流,支持通道可发地区设置,通道路由分组&#x…...

Java“牵手”阿里巴巴店铺所有商品API接口数据,通过店铺ID获取整店商品详情数据,阿里巴巴店铺所有商品API申请指南
阿里巴巴平台店铺所有商品数据接口是开放平台提供的一种API接口,通过调用API接口,开发者可以获取阿里巴巴整店的商品的标题、价格、库存、月销量、总销量、库存、详情描述、图片、价格信息等详细信息 。 获取店铺所有商品接口API是一种用于获取电商平台…...

【Sql】把数据库字段用函数根据逗号分裂成列表,然后判断列表中是否包含目标值
【Sql】把数据库字段用函数根据逗号分裂成列表,然后判断列表中是否包含目标值 【1】问题描述【2】Oracle内置函数解决【3】mysql的内置函数INSTR()【4】mysql的内置函数FIND_IN_SET() 【1】问题描述 数据库中【库信息db】和【集群信息cluster】是一对多的关系&…...
docker基本命令记录
Docker 是一个开源的容器技术,它允许开发人员将应用程序及其所有依赖项打包到一个容器中,然后轻松地在任何地方部署和运行。以下是 Docker 的一些基本操作: 基础操作: 启动 Docker:service docker start停止 Docker:service docker stop查看 Docker 信息:docker info容器操作…...

web之利用延迟实现复杂动画、animation
文章目录 效果图htmlstyleJavaScript 效果图 html <div class"container"><div class"ball"></div><input type"range" min"0" max"1" step"0.01" /> </div>style body {display…...

TCP 和 UDP 的区别、TCP 是如何保证可靠传输的?
先来介绍一些osi七层模型 分为应用层、表示层、会话层、运输层、网络层、链路层、物理层。 应用层(数据):确定进程之间通信的性质以及满足用户需要以及提供网络和用户应用,为应用程序提供服务,DNS,HTTP,HTTPS…...

鼠标悬停阴影的效果被旁边div挡住的解决办法
出现的问题 需求要求鼠标悬停某个图片上有阴影效果,但阴影被旁边相邻的div挡住了,如图所示 解决方案 给悬停的这块div增加2个css属性 $(this).css(position, relative); $(this).css(z-index, 200);新的效果如图所示 一直写后端,前端的…...
Go用两个协程交替打印100以内的奇偶数
方式1(使用无缓冲的channel) package mainimport ( "fmt" "time")var flagChan make(chan int)func wokr1() { for i : 1; i < 100; i { flagChan <- 666 // 塞入 if i%2 1 { fmt.Println("协程1打印:", i) …...

CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...

前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...