算法通关村-----堆在查找和排序中的应用
数组中的第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) …...

边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...

基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...

抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...