当前位置: 首页 > 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;复选框都发挥着重要作用。然…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

《信号与系统》第 6 章 信号与系统的时域和频域特性

目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...