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

数组中的第K个最大元素 ---- 分治-快排

题目链接

题目:

分析:

  • 这道题很明显是一个top-K问题, 我们很容易想到用堆排序来解决, 堆排序的时间复杂度是O(N*logN), 不符合题意, 所以我们可以用另一种方法:快速选择算法, 他的时间复杂度为O(N)
  • 快速选择算法, 其实是基于快排, 进行修改而成, 我们还是使用将"将数组分成三块" 的方法来实现快排排序数组 ---- 分治-快排-CSDN博客
  • 此时我们每一块的元素个数分别设为a b c
  • 情况一: 如果第k个最大元素落在>key的区间, 说明此时c一定是>=k的, 此时只需要去[right, r]区间去找第k个最大元素即可
  • 情况二: 如果第k个最大元素落在=key的区间, 那么b+c一定是>=k的, 此时只需要返回key即可, 因为这个区间都是key
  • 情况三: 如果不是上述两种情况, 那么第k个最大元素一定落在<key的区间, , 此时需要去[l, left]区间去找, 但是我们要找的是第k-b-c大的元素, 因为我们舍去了=key和>key的区间

代码:

class Solution {public int findKthLargest(int[] nums, int k) {return qsort(nums, 0, nums.length - 1, k);}public int qsort(int[] nums, int l, int r, int k) {if (l == r)return nums[l];int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1;int right = r + 1;int i = l;while (i < right) {if (nums[i] < key) {swap(nums, i++, ++left);} else if (nums[i] == key) {i++;} else {swap(nums, i, --right);}}// [l,left] [left + 1, right - 1] [right, r]int c = r - right + 1;int b = right - left - 1;if (c >= k)return qsort(nums, right, r, k);else if (b + c >= k)return key;elsereturn qsort(nums, l, left, k - b - c);}public void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}

相关文章:

数组中的第K个最大元素 ---- 分治-快排

题目链接 题目: 分析: 这道题很明显是一个top-K问题, 我们很容易想到用堆排序来解决, 堆排序的时间复杂度是O(N*logN), 不符合题意, 所以我们可以用另一种方法:快速选择算法, 他的时间复杂度为O(N)快速选择算法, 其实是基于快排, 进行修改而成, 我们还是使用将"将数组分…...

函数或变量 ‘tfrstft‘ 无法识别

参考博客 Matlab时频工具箱tftb下载及安装_tftb工具箱-CSDN博客 解决。...

在推荐四款软件卸载工具,让流氓软件无处遁形

Revo Uninstaller Revo Uninstaller是一款电脑软件、浏览器插件卸载软件&#xff0c;目前已经有了17年的历史了。可以扫描所有window用户卸载软件后的残留物&#xff0c;并及时清理&#xff0c;避免占用电脑空间。 Revo Uninstaller可以通过命令行卸载软件&#xff0c;可以快速…...

「前端+鸿蒙」核心技术HTML5+CSS3(十一)

1、CSS3 简介 CSS3 是层叠样式表的最新标准,它引入了许多新特性来增强网页的表现力。CSS3 不仅增强了现有CSS属性的功能,还引入了新的布局方式、动画、渐变、阴影、边框效果等。 2、CSS3 长度单位 CSS3 引入了一些新的单位,包括但不限于: vw(视口宽度的百分比)vh(视口…...

【高频】如何优化一个SQL语句

使用合适的索引&#xff1a;确保查询中涉及的字段上有合适的索引&#xff0c;避免全表扫描。可以通过 EXPLAIN 命令来查看查询执行计划&#xff0c;判断是否使用了索引。 避免使用通配符查询&#xff1a;尽量避免在查询条件中使用通配符&#xff08;如 %&#xff09;&#xff…...

Oracle EBS AP发票创建会计科目提示:APP-SQLAP-10710:无法联机创建会计分录

系统版本 RDBMS : 12.1.0.2.0 Oracle Applications : 12.2.6 问题症状: 提交“创建会计科目”请求提示错误信息如下: APP-SQLAP-10710:无法联机创建会计分录。 请提交应付款管理系统会计流程,而不要为此事务处理创建会计分录解决方法 数据修复SQL脚本: UPDATE ap_invoi…...

T-Pot多功能蜜罐实践@debian12@FreeBSD

T-Pot介绍 T-Pot是一个集所有功能于一身的、可选择分布式的多构架&#xff08;amd64&#xff0c;arm64&#xff09;蜜罐平台&#xff0c;支持20多个蜜罐和很多可视化选项&#xff0c;使用弹性堆栈、动画实时攻击地图和许多安全工具来进一步改善欺骗体验。GitHub - telekom-sec…...

Sed流编辑器总结

sed 是 Unix 和 Linux 系统中的一个强大的流编辑器。它用于对文本进行基本的修改和处理。以下是关于 sed 的详细解说&#xff0c;包括其基本语法&#xff0c;常见用法和一些高级用法。 基本语法 sed [选项] 命令 输入文件常见选项 -e&#xff1a;指定要执行的 sed 命令。-f&a…...

智合同丨AIGC如何助力合同智能应用

#AIGC #合同智能应用 #智合同 AIGC&#xff0c;即人工智能生成内容技术&#xff08;Artificial Intelligence Generated Content&#xff09;&#xff0c;近期在各个领域发展可谓是如火如荼&#xff0c;那么它在合同智能应用方面可以提供哪些助力&#xff1f; 让我们和智合…...

CSRF 令牌的生成过程和检查过程

在 Django 中,CSRF 令牌的生成和检查过程是通过 Django 的 CSRF 中间件 (CsrfViewMiddleware) 和模板标签 ({% csrf_token %}) 自动处理的。以下是详细的生成和检查过程: CSRF 令牌的生成过程 用户访问页面: 当用户第一次访问页面时,Django 会为用户创建一个会话。如果用户…...

计算机网络学习记录 网络层 Day4(下)

计算机网络学习记录 网络层 Day4 &#xff08;下&#xff09; 你好,我是Qiuner. 为记录自己编程学习过程和帮助别人少走弯路而写博客 这是我的 github https://github.com/Qiuner ⭐️ ​ gitee https://gitee.com/Qiuner &#x1f339; 如果本篇文章帮到了你 不妨点个赞吧~ 我…...

3、前端本地环境搭建

前端本地环境搭建 安装node [node下载地址] https://nodejs.org/en/download/prebuilt-installer 选择LTS的版本进行下载 下载后直接双击点击&#xff0c;选择自己想要安装到的目录一直点下一步即可&#xff08;建议不要安装到c盘&#xff09; 安装完成后配置环境变量&am…...

Python爬取城市空气质量数据

Python爬取城市空气质量数据 一、思路分析1、寻找数据接口2、发送请求3、解析数据4、保存数据二、完整代码一、思路分析 目标数据所在的网站是天气后报网站,网址为:www.tianqihoubao.com,需要采集武汉市近十年每天的空气质量数据。先看一下爬取后的数据情况: 1、寻找数据…...

【MyBatisPlus条件构造器】

文章目录 什么是条件构造器&#xff1f;使用步骤1. 引入 MyBatisPlus 依赖2. 创建实体类3. 使用条件构造器查询4. 执行查询 示例代码 什么是条件构造器&#xff1f; 条件构造器是 MyBatisPlus 提供的一种灵活的查询条件设置方式&#xff0c;它可以帮助开发者构建复杂的查询条件…...

容器多机部署eureka及相关集群服务出现 Request execution failed with message: AuthScheme is null

预期部署方案&#xff1a;两个eureka三个相关应用 注册时应用出现&#xff1a;Request execution failed with message: Cannot invoke “Object.getClass()” because “authScheme” is null&#xff0c;一开始认为未正确传递eureka配置的账户密码&#xff0c;例&#xff1a;…...

Qt Graphics View Framework 使用教程

欢迎来到 Qt Graphics View Framework 的世界&#xff01;本教程将引导您了解这一强大工具的基础知识&#xff0c;并教您如何开始使用它来创建丰富的 2D 图形界面。无论您是编程新手还是经验丰富的开发者&#xff0c;本教程都将帮助您快速上手。 基本概念 Qt Graphics View F…...

【调试笔记-20240606-Linux-为 OpenWrt 的 nginx 服务器添加Shell CGI 支持】

调试笔记-系列文章目录 调试笔记-20240606-Linux-为 OpenWrt 的 nginx 服务器添加Shell CGI 支持 文章目录 调试笔记-系列文章目录调试笔记-20240606-Linux-为 OpenWrt 的 nginx 服务器添加Shell CGI 支持 前言一、调试环境操作系统&#xff1a;Windows 10 专业版调试环境调试…...

flink实战--⼤状态作业调优实践指南-Flink SQL 作业篇

简介 作为一种特定领域语言,SQL 的设计初衷是隐藏底层数据处理的复杂性,让用户通过声明式语言来进行数据操作。而Flink SQL 由于其架构的特殊性,在实现层面通常需引入状态后端 配合 checkpoint 来保证计算结果的最终一致性。目前 Flink SQL 生成状态算子的策略由优化器根据配…...

数据结构:顺序串

目录 1.顺序串是什么&#xff1f; 2.顺序串常见操作和应用 3.包含头文件 4.结点设计 5.接口函数定义 6.接口函数实现 7.顺序串测试案列 顺序串是什么&#xff1f; 顺序串&#xff0c;用于存储和操作字符串。在顺序串中&#xff0c;字符串被存储在一个连续的内存块中&#xff0c…...

掌握复选框(Checkbox)的奥秘:全选与反选功能实现

前言&#xff1a; 在网页设计中&#xff0c;复选框&#xff08;Checkbox&#xff09;是一种常见且实用的交互元素&#xff0c;它允许用户从一系列选项中选择多个项。无论是电子商务网站上的商品筛选&#xff0c;还是在线表单的数据收集&#xff0c;复选框都发挥着重要作用。然…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

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

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…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...