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

堆--数组中第K大元素

如果对于堆不是太认识,请点击:堆的初步认识-CSDN博客

解题思路:

/*** <h3>求数组中第 K 大的元素</h3>* <p>* 解体思路* <ol>*     1.向小顶堆放入前k个元素*     2.剩余元素*         若 <= 堆顶元素, 则略过*         若 > 堆顶元素, 则替换堆顶元素*     3.这样小顶堆始终保留的是到目前为止,前K大的元素*     4.循环结束, 堆顶元素即为第K大元素* </ol>*/

小顶堆(可删去用不到代码)

class MinHeap {int[] array;int size;public MinHeap(int capacity) {array = new int[capacity];}private void heapify() {for (int i = (size >> 1) - 1; i >= 0; i--) {down(i);}}public int poll() {swap(0, size - 1);size--;down(0);return array[size];}public int poll(int index) {swap(index, size - 1);size--;down(index);return array[size];}public int peek() {return array[0];}public boolean offer(int offered) {if (size == array.length) {return false;}up(offered);size++;return true;}public void replace(int replaced) {array[0] = replaced;down(0);}private void up(int offered) {int child = size;while (child > 0) {int parent = (child - 1) >> 1;if (offered < array[parent]) {array[child] = array[parent];} else {break;}child = parent;}array[child] = offered;}private void down(int parent) {int left = (parent << 1) + 1;int right = left + 1;int min = parent;if (left < size && array[left] < array[min]) {min = left;}if (right < size && array[right] < array[min]) {min = right;}if (min != parent) {swap(min, parent);down(min);}}// 交换两个索引处的元素private void swap(int i, int j) {int t = array[i];array[i] = array[j];array[j] = t;}
}

题解

public int findKthLargest(int[] numbers, int k) {MinHeap heap = new MinHeap(k);for (int i = 0; i < k; i++) {heap.offer(numbers[i]);}for (int i = k; i < numbers.length; i++) {if(numbers[i] > heap.peek()){heap.replace(numbers[i]);}}return heap.peek();
}

注意哦:求数组中的第 K 大元素,使用堆并不是最佳选择,可以采用快速选择算法

 

相关文章:

堆--数组中第K大元素

如果对于堆不是太认识&#xff0c;请点击&#xff1a;堆的初步认识-CSDN博客 解题思路&#xff1a; /*** <h3>求数组中第 K 大的元素</h3>* <p>* 解体思路* <ol>* 1.向小顶堆放入前k个元素* 2.剩余元素* 若 < 堆顶元素, 则略过* …...

ipad使用技巧

1、goodnotes中批量导入pdf文件 法一&#xff1a; 直接参考视频&#xff1a; 【目前为止所知iPad上goodnotes批量导入网盘文件最快的方法】 大致步骤&#xff1a;pdf文件传到百度网盘&#xff0c;然后ES软件登录百度网盘&#xff0c;在goodnotes中导入&#xff0c;选择ES&a…...

Windows系统上使用CLion远程开发Linux程序

CLion远程开发Linux程序 情景说明Ubuntu配置CLion配置同步 情景说明 在Windows系统上使用CLion开发Linux程序&#xff0c;安装CLion集成化开发环境时会自动安装cmake、mingw&#xff0c;代码提示功能也比较友好。 但是在socket开发时&#xff0c;包含sys/socket.h头文件时&am…...

github搜索技巧

指定语言 language:java 比如我要找用java写的含有blog的内容 搜索项目名称包含关键词的内容 vue in:name 其他如项目描述跟项目文档&#xff0c;如下 组合使用 vue in:name,description,readme 根据Star 或者fork的数量来查找 总结 springboot vue stars:>1000 p…...

Python生成器

生成器 Generators 要理解生成器&#xff0c;首先要理解迭代器&#xff0c;迭代器由以下三个部分组成&#xff1a; 可迭代对象&#xff08;iterable&#xff09;迭代器&#xff08;iterator&#xff09;迭代&#xff08;iteration&#xff09; 1. 可迭代对象 只要定义了可以…...

flutter开发实战-使用FutureBuilder异步数据更新Widget

flutter开发实战-使用FutureBuilder异步数据更新Widget 在开发过程中&#xff0c;经常遇到需要依赖异步数据更新Widget的情况&#xff0c;如下载图片后显示Widget&#xff0c;获取到某个数据时候&#xff0c;显示在对应的UI界面上&#xff0c;都可以使用FutureBuilder异步数据…...

1.2 数据模型

思维导图&#xff1a; 前言&#xff1a; **1.2.1 什么是模型** - **定义**&#xff1a;模型是对现实世界中某个对象特征的模拟和抽象。例如&#xff0c;一张地图、建筑设计沙盘或精致的航模飞机都可以视为具体的模型。 - **具体模型与现实生活**&#xff1a;具体模型可以很容…...

【实用工具】谷歌浏览器插件开发指南

谷歌浏览器插件开发指南涉及以下几个方面&#xff1a; 1. 开发环境准备&#xff1a;首先需要安装Chrome浏览器和开发者工具。进入Chrome应用商店&#xff0c;搜索“Extensions Reloader”和“Manifest Viewer”两个插件进行安装&#xff0c;这两个插件可以方便开发和调试。 2…...

应用层协议——DNS、DHCP、HTTP、FTP

目录 1、DNS 协议 1-1&#xff09;Hosts 文件 1-2&#xff09;DNS 系统 1-3&#xff09;域名的组成、分类和树状结构 1-4&#xff09;DNS 域名服务器类型 1-5&#xff09;DNS 查询方式 1-6&#xff09;DNS 域名解析的一般步骤 1-7&#xff09;对象类型与资源记录 2、D…...

XML文件读写

0、.pro文件添加依赖 QT xml1、使用 QDomDocument 方式 #include <QtXml/QDomDocument> #include <QtXml/QDomProcessingInstruction> #include <QtXml/QDomElement> #include <QFile> #include <QTextStream> #include <QDebug>bo…...

Win11 安装 Vim

安装包&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1Ru7HhTSotz9mteHug-Yhpw?pwd6666 提取码&#xff1a;6666 双击安装包&#xff0c;一直下一步。 配置环境变量&#xff1a; 先配置系统变量中的path&#xff1a; 接着配置用户变量&#xff1a; 在 cmd 中输入…...

Mac电脑BIM建模软件 Archicad 26 for Mac最新

ARCHICAD 软件特色 智能化 在2D CAD中&#xff0c;所有的建筑构件都由线条构成和表现&#xff0c;仅仅是一些线条的组合而已&#xff0c;当我们阅读图纸的时候是按照制图规范来读取这些信息。我们用一组线条表示平面中的窗&#xff0c;再用另一组不同的线条在立面中表示同一个…...

JavaEE-网络编程套接字(UDP/TCP)

下面写一个简单的UDP客户端服务器流程 思路&#xff1a; 对于服务器端&#xff1a;读取请求&#xff0c;并解析–> 根据解析出的请求&#xff0c;做出响应(这里是一个回显&#xff0c;)–>把响应写回客户端 对于客户端&#xff1a;从控制台读取用户输入的内容–>从控制…...

微服务技术栈-Gateway服务网关

文章目录 前言一、为什么需要网关二、Spring Cloud Gateway三、断言工厂和过滤器1.断言工厂2.过滤器3.全局过滤器4.过滤器执行顺序 四、跨域问题总结 前言 在之前的文章中我们已经介绍了微服务技术中eureka、nacos、ribbon、Feign这几个组件&#xff0c;接下来将介绍另外一个组…...

函数形状有几种定义方式;操作符infer的作用

在 TypeScript 中&#xff0c;函数形状可以用多种方式进行定义。下面介绍了几种常用的函数形状定义方式&#xff1a; 函数声明&#xff1a; function add(a: number, b: number): number {return a b; }在函数声明中&#xff0c;我们直接使用 function 关键字来声明函数&…...

Java / MybatisPlus:JSON处理器的应用,在实体对象中设置对象属性,对象嵌套对象

1、数据库设计 2、定义内部的实体类 /*** Author lgz* Description* Date 2023/9/30.*/ Data // 静态构造staticName&#xff0c;方便构造对象并赋予属性 AllArgsConstructor(staticName "of") NoArgsConstructor ApiModel(value "亲友", description …...

力扣 -- 1027. 最长等差数列

解题步骤&#xff1a; 参考代码&#xff1a; class Solution { public:int longestArithSeqLength(vector<int>& nums) {int nnums.size();int ret2;unordered_map<int,int> hash;//这里可以先把nums[0]存进哈希表中&#xff0c;方便后面i从1开始遍历hash[num…...

正则验证用户名和跨域postmessage

正则验证用户名 字母数字符号大小写8-14匹配用户名的 <!DOCTYPE html> <html> <head><meta charset"utf-8"><meta name"viewport" content"widthdevice-width, initial-scale1"><title>form</title> …...

jsbridge实战1:xcode swift 构建iOS app

[[toc]] 环境安装 macOs: 10.15.5 xcode: 11.6 demo:app 创建 hello world iOS app 创建工程步骤 选择&#xff1a;Create a new Xcode project选择&#xff1a;iOS-> single View App填写&#xff1a; project name: swift-app-helloidentifer: smile 包名language: s…...

零基础部署nginx mysql springboot

参考&#xff1a;写给开发人员看的Docker干货&#xff0c;零基础部署nginx mysql springboot 一、连接linux 阿里云 参考&#xff1a;部署到Linux 可能需要购买&#xff1a;购买链接 二、安装docker # 先切换到root用户下 sudo su# 更新apt-get&#xff0c;保证apt-get最新…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...