有序矩阵中第 K 小的元素
题目链接
有序矩阵中第 K 小的元素
题目描述
注意点
- 每行和每列元素均按升序排序
- 找到一个内存复杂度优于 O(n²) 的解决方案
解答思路
- 使用二分查找,思路为:
(1)因为左上角的元素值更小,右下角的元素值更大,先将left设置为左上角元素的值,right设置为右下角元素的值;
(2)判断不大于left和right中间值mid的元素数量sum;
(3)如果sum小于k,则将left设置为mid + 1,否则将right设置为mid。 - 不断重复上述过程,直到满足sum等于k时right的最小值,此时left等于right,且right是大于等于矩阵中K个元素的临界点,所以矩阵中一定会有一个元素等于right(否则说明并没有找到sum等于k时right的最小值),right也就是有序矩阵中第 K 小的元素
代码
class Solution {int n;public int kthSmallest(int[][] matrix, int k) {n = matrix.length;int left = matrix[0][0];int right = matrix[n - 1][n - 1];while (left < right) {int mid = left + (right - left) / 2;int sum = countLessThanMid(matrix, mid);if (sum < k) {left = mid + 1;} else {right = mid;}}return left;}public int countLessThanMid(int[][] matrix, int mid) {int sum = 0;for (int i = 0; i < n; i++) {// 如果左上角都大于mid,则一定没有小于等于mid的元素存在if (matrix[i][0] > mid) {return sum;}// 如果右上角都小于等于mid,则该行所有元素都小于等于midif (matrix[i][n - 1] <= mid) {sum += n;continue;}// 其余情况查找改行小于等于mid的元素for (int j = 0; j < n; j++) {if (matrix[i][j] > mid) {break;}sum++;}}return sum;}
}
关键点
- 二分查找的思路
- 怎么找到sum等于k时right的最小值
- 当right - left=1,且两个数都是负数的时候,求mid时会等于right的值,此时如果sum >= k,则会一直卡在循环中无法跳出,需要保证这种特殊情况求mid也是left,所以求mid时使用left + (right - left) / 2
相关文章:
有序矩阵中第 K 小的元素
题目链接 有序矩阵中第 K 小的元素 题目描述 注意点 每行和每列元素均按升序排序找到一个内存复杂度优于 O(n) 的解决方案 解答思路 使用二分查找,思路为: (1)因为左上角的元素值更小,右下角的元素值更大…...
Nginx详细介绍(并从技术层面深度剖析)
nginx介绍 1.nginx 介绍2.nginx的优势3.Nginx VS Apache3.1.内核、语言、诞生时间比较3.2.功能比较3.3.Nginx 相对 apache 的优点 4.Nginx为什么有这么多的优势?4.1.IO多路复用(I/O multiplexing【多并发】)4.2.nginx的驱动模型介绍4.3.nginx…...
单元测试基本概念
单元测试一般是开发来做的,但是因为业务需要也曾涉及过单元测试。目前就单元测试的基础概念做下总结。 一、 单元测试定义: 单元测试是软件开发中的一种测试方法,用于验证程序中的最小可测单元——即代码中的单个函数、方法或模块。单元测试…...
ECTouch 电商微信小程序 SQL注入漏洞复现(CVE-2023-39560)
0x01 产品简介 ECTouch是一款开源的电商系统,为中小企业提供最佳的新零售解决方案 0x02 漏洞概述 ECTouch 电商系统 /ectouch-main/include/apps/default/helpers/insert.php 文件中第285行的 insert_bought_notes 函数中,传入的 $arr[id] 参数未进行验证和过滤,导致未经…...
MCM备赛笔记——熵权法
Key Concept 熵权法是一种基于信息熵概念的权重确定方法,用于多指标决策分析中。信息熵是度量信息量的不确定性或混乱程度的指标,在熵权法中,它用来反映某个指标在评价过程中的分散程度,进而确定该指标的权重。指标的分散程度越高…...
vscode设置terminal的最大行数
今天跑代码出现一个问题,就是整个程序跑完,整个程序的输出信息过多,最开始输出的信息已经被vscode的缓存冲掉了,只能看到最后的一部分,具体的原因是vscode的terminal默认只能保存1000行的信息,所以如果想保…...
kafka hang 问题记录
参考文档 https://cloud.tencent.com/developer/article/1821477 9092端口 端口9092通常与Apache Kafka关联。 Kafka是一个开源的分布式事件流平台,用于构建实时的数据管道和流应用。 它能够处理任意大小的数据,以容错的方式处理数据流。 在默认配置…...
Jmeter-BeanShell脚本中for循环里面使用random随机数函数,每次生成的都一样
预想的是每次循环生成的随机数不一样,但实际使用Random函数生成的是重复的。 以下是部分原代码: List updateList new ArrayList(); for(Object o: fieldList){Map map new HashMap();map.put("id", o.get("id"));map.put("…...
高级编程。JavaScript中有哪些类型转换机制?
一、概述 前面我们讲到,JS中有六种简单数据类型:undefined、null、boolean、string、number、symbol,以及引用类型:object 但是我们在声明的时候只有一种数据类型,只有到运行期间才会确定当前类型 let x y ? 1 : …...
Linux系统下常用软件安装汇总,包括mysql,java,git,redis等
01.环境搭建 1.安装列表 MySQL 5.7.11 Java 1.8 Apache Maven 3.6 tomcat8.5 git Redis Nginx python docker 2.安装mysql 1.拷贝mysql安装文件到Linux的某个目录下 2.解压Linux安装包:tar -xvzf mysql-5.7.32-linux-glibc2.12-x86_64.tar.gz 3.进入解压后…...
【Linux】——期末复习题(一)
🎃个人专栏: 🐬 算法设计与分析:算法设计与分析_IT闫的博客-CSDN博客 🐳Java基础:Java基础_IT闫的博客-CSDN博客 🐋c语言:c语言_IT闫的博客-CSDN博客 🐟MySQL:…...
【论文阅读】Speech Driven Video Editing via an Audio-Conditioned Diffusion Model
DiffusionVideoEditing:基于音频条件扩散模型的语音驱动视频编辑 code:GitHub - DanBigioi/DiffusionVideoEditing: Official project repo for paper "Speech Driven Video Editing via an Audio-Conditioned Diffusion Model" paper&#…...
【华为 ICT HCIA eNSP 习题汇总】——题目集4
1、(多选)网络中出现故障后,管理员通过排查发现某台路由器的配置被修改了,那么管理员应该采取哪些措施来避免这种状况再次发生? A、管理员应该通过配置 ACL 来扩展只有管理员能够登录设备 B、管理员应该在路由的管理端…...
hadoop-common: CMake failed with error code 1
问题 在编译hadoop源码时遇到如下错误 hadoop-common: CMake failed with error code 1 看了这个错误表示一脸懵逼 排查 在mvn 的命令中增加 -X 和 -e mvn clean package -e -X -Pdist,native -DskipTests -Dmaven.javadoc.skip -Dopenssl.prefix/usr/local/bin/openssl 在…...
【面试】-科大讯飞日常实习面试
科大讯飞日常实习面试 提问的问题 面试30min,基本就是介绍项目以及提问java八股文,没有算法题 java保证线程安全的方法 需要根据具体场景选择合适的方法来保证线程安全。java中的异步请求如何实现你的SpringBoot项目怎么匹配在线人数请说出spring springMVC springboot之间的…...
MySQL 数据加密
MySQL 数据加密主要用于保护存储在数据库中的敏感信息,如用户密码、个人身份信息等。MySQL 提供了多种数据加密方法,主要包括: 对称加密: AES_ENCRYPT() 和 AES_DECRYPT() 函数:MySQL 支持使用高级加密标准(…...
风丘科技为您提供完整的ADAS测试方案
一 方案概述 随着5G通讯与互联网的快速发展,智能汽车和ADAS辅助系统的研究与发展在世界范围内也在如火如荼地进行。风丘科技紧跟时代脚步,经多年积累沉淀,携手整车厂与高校共同研发打造出了一套完整且适用于国内ADAS测试的系统方案。 | ADAS…...
深入理解Rust基本类型
文章目录 一、概述二、数值类型2.1、整数类型2.2、浮点类型2.3、数字运算2.4、位运算2.5、序列(Range)2.6、有理数和复数 三、字符、布尔、单元类型3.1、字符类型3.2、布尔类型(bool)3.3、单元类型 团队博客: 汽车电子社区 一、概…...
cloudflare加速方法
一、使用Cloudflare优速域名或IP,实现国内访问加速 二、使用境外CN2、GIA等直连联网的VPS:如华纳云、彩红云等(未测试) 三、页面托管方案: 四、cloudflare合作伙伴计划:自定义cdn节点、dnspod提供的dns解析…...
密码学学习笔记(二十四):TCP/IP协议栈
TCP/IP协议栈的基础结构包括应用层、传输层、网络层、数据链路层和物理层。 应用层 应用层位于TCP/IP协议栈的最顶层,是用户与网络通信的接口。这一层包括了各种高级应用协议,如HTTP(用于网页浏览)、FTP(用于文件传输…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
