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

LeetCode 378 有序矩阵中第K小的元素

题目信息

LeetoCode地址: . - 力扣(LeetCode)

题解内容大量转载于:. - 力扣(LeetCode)

题目理解

题意很直观,就是求二维矩阵中所有元素排序后第k小的数。

最小堆写法

该写法不再赘述,维护一个大小为k的小顶堆,遍历矩阵所有元素进行入堆操作。

时间复杂度:O(nlogk)

空间复杂度:O(k)

class Solution {public int kthSmallest(int[][] matrix, int k) {PriorityQueue<Integer> heap = new PriorityQueue<>((a,b) -> (int)b-(int)a);for (int i = 0; i<matrix.length; i++) {for (int j = 0; j<matrix[0].length;j++) {if (heap.size() < k) {heap.offer(matrix[i][j]);} else if (matrix[i][j] < heap.peek()) {heap.poll();heap.offer(matrix[i][j]);}}}return heap.peek();}
}

二分写法

由于矩阵在行和列上都是有序的,因此左上角的元素matrix[0][0]一定是最小的,右下角的元素matrix[n-1][n-1]一定是最大的。这两个元素,我们分别记为l 和 r.

以下图为例:

可以发现, 任取一个数mid满足l<=mid<=r, 那么矩阵中不大于mid的数,肯定都分布在矩阵的左上角。

例如下图, 取mid=8:

我们可以看出,矩阵中大于mid的数和不大于mid的数分别形成了两个版本,沿着一条锯齿线将这个矩形分隔开。其中左上角板块的大小即为不大于mid的数的数量。

我们只需沿着这条锯齿线走一遍即可计算出这两个板块的大小,自然就统计出这个矩阵中不大于mid的数的个数了。

同样以mid=8举例,走法如下:

走法可以总结如下:

  • 初始位置在matrix[n-1][0] (即左下角);
  • 设当前位置为matrix[i][j], 若matrix[i][j] <= mid, 则将当前所在列的不大于mid的数的数量(即i+1)累加到答案中,并向右移动,否则向上移动;
  • 不断移动,直到走出格子为止。

可以发现,这样的走法时间复杂度为O(n),即我们可以线性的计算对于任意一个mid,矩阵中有多少数不大于它。这满足了二分查找的性质。

不妨设答案为x, 那么可以直到l<=x<=r, 这样就确定了二分查找的上下界。

对于每次猜测的答案mid, 计算矩阵中有多少数不大于 mid:

  • 如果数量不少于k, 那么说明最终答案不大于mid;
  • 如果数量小于k, 那么说明最终答案大于mid.

这样我们就可以计算出最终的结果x了。

时间复杂度: O(nlogn)

额外空间复杂度: O(1)

class Solution {public int kthSmallest(int[][] matrix, int k) {int h = matrix.length, w = matrix[0].length;int l = matrix[0][0], r = matrix[h-1][w-1];while (l < r) {int mid = l + (r-l)/2;if (check(matrix, mid, k)) {r = mid;} else {l = mid+1;}}return l;}public boolean check(int[][] matrix,int mid, int k) {int i = matrix.length-1, j = 0;int count = 0;while (i >=0 && j < matrix[0].length) {if (matrix[i][j] <= mid) {count += i+1;j++;} else {i--;}}return count >= k; }
}

相关文章:

LeetCode 378 有序矩阵中第K小的元素

题目信息 LeetoCode地址: . - 力扣&#xff08;LeetCode&#xff09; 题解内容大量转载于&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 题目理解 题意很直观&#xff0c;就是求二维矩阵中所有元素排序后第k小的数。 最小堆写法 该写法不再赘述&#xff0c;维护…...

Vue3(domdiff)最长递归子序列求解简易版(超简单)

Vue3&#xff08;domdiff&#xff09;最长递归子序列求解简易版 ⚠️ 关键词&#xff08;每一个都需要理解&#xff09;js 代码实现写完感想欢迎关注 ⚠️ 关键词&#xff08;每一个都需要理解&#xff09; 动态规划&#xff08;O(N^2)&#xff09;&#xff08;不提倡&#xf…...

LLaMA-Factory+qwen多轮对话微调

LLaMA-Factory地址&#xff1a;https://github.com/hiyouga/LLaMA-Factory/blob/main/README_zh.md qwen地址&#xff1a;https://huggingface.co/Qwen/Qwen-7B-Chat/tree/main 数据准备 数据样例 [ {"id": "x3959", "conversations": [{&qu…...

邦芒面试:如何在面试中巧妙回答自己的缺点

在面试中&#xff0c;被问及自己的缺点时&#xff0c;如何巧妙回答是一门学问。恰当的回答不仅能够展示你的自我认知&#xff0c;还能让面试官看到你的成长潜力和积极态度。 首先&#xff0c;切忌谈一些看似缺点实则优点的话题&#xff0c;如追求完美、待人接物太客气等。这些…...

Android:身份证识别功能实现

说明&#xff1a; 此文使用华为SDK、百度SDK、百度在线API三种方式实现。 一、使用华为SDK实现身份证识别&#xff1a; 说明&#xff1a;免费&#xff0c;不需要联网。 1.AndroidManifest.xml添加权限&#xff1a;<uses-permission android:name"android.permissio…...

MacOS安装Homebrew教程

安装 Homebrew 是在 macOS 上管理软件包的一种简便方法。以下是安装 Homebrew 的步骤&#xff1a; 打开终端&#xff1a;你可以通过在 Spotlight 搜索栏中输入“终端”并按下回车键来打开 macOS 的终端应用程序。 执行安装命令&#xff1a;在终端中粘贴以下命令并按下回车键执…...

laravel如何通过DB获取一条数据并转成数组

在 Laravel 中&#xff0c;你可以使用原生数据库查询构建器&#xff08;DB facade&#xff09;来获取一条数据&#xff0c;并将其转换为数组。这可以通过在查询链的末尾调用 first() 方法后&#xff0c;使用 toArray() 方法来实现。first() 方法会返回一个 StdClass 对象&#…...

ENSP USG防火墙接入虚拟机;开启Web访问;

1.添加防火墙及云&#xff0c;启动防火墙&#xff1b; 2.配置桥接网卡&#xff1b; 默认账户&#xff1a;admin 默认密码&#xff1a;Admin123 #第一次登陆需修改密码&#xff1b; 默认G0/0/0口为管理口&#xff0c;而在模拟器中进入防火墙的web需如下配置&#xff1a; 配置 …...

数据结构算法题(力扣)——链表

以下题目建议大家先自己动手练习&#xff0c;再看题解代码。这里只提供一种做法&#xff0c;可能不是最优解。 1. 移除链表元素&#xff08;OJ链接&#xff09; 题目描述&#xff1a;给一个链表的头节点 head 和一个整数 val &#xff0c;删除链表中所有满足值等于 val 的节点…...

LeetCode---391周赛

题目列表 3099. 哈沙德数 3100. 换水问题 II 3101. 交替子数组计数 3102. 最小化曼哈顿距离 一、哈沙德数 简单的模拟题&#xff0c;代码如下 class Solution { public:int sumOfTheDigitsOfHarshadNumber(int x) {int s 0, tmp x;while(tmp){stmp%10;tmp/10;}return x…...

微信小程序的页面交互2

一、自定义属性 &#xff08;1&#xff09;定义&#xff1a; 微信小程序中的自定义属性实际上是由data-前缀加上一个自定义属性名组成。 &#xff08;2&#xff09;如何获取自定义属性的值&#xff1f; 用到target或currentTarget对象的dataset属性可以获取数据 &#xff…...

【VSCode】修改插件地址

不想放在原始C盘下面C:\Users\{用户}\.vscode\extensions为了后续存储空间考虑&#xff0c;想通过添加环境变量创建名为VSCODE_EXTENSIONS的环境变量&#xff0c;内容指向vs Code扩展所在目录即可 直接配置环境变量&#xff0c;不要在有空格的文件夹下面 变量名称&#xff1a;…...

自然语言处理NLP概述

大家好&#xff0c;自然语言处理(NLP)是计算机科学领域与人工智能领域中的一个重要方向&#xff0c;其研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法。本文将从自然语言处理的本质、原理和应用三个方面&#xff0c;对其进行概述。 一、NLP的本质 NLP是一种…...

计算机网络——37认证

认证 目标&#xff1a;Bob需要Alice证明他的身份 Protocol ap1.0&#xff1a;Alice说"A am Alice" 可能出现的问题&#xff1a; 在网络上Bob看不到Alice&#xff0c;因此Trudy可以简单的声称他是Alice 认证&#xff1a;重新尝试 Protocol ap2.0&#xff1a;Alice…...

Java中利用BitMap位图实现海量级数据去重

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Java全栈-专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 目录 前言 什么是BitMap&#xff1f;有什么用&#xff1f; 基本概念 位图的优势 …...

Linux知识点记录

Linux知识点记录 1. 后台运行应用程序方法一&#xff1a;&方法二&#xff1a;nohup & 2. 一个shell脚本中执行多个应用程序3. 2>&14. shell脚本清除日志5. 通过grep查找匹配字符串 1. 后台运行应用程序 参考文章&#xff1a;https://blog.csdn.net/Pan_peter/…...

js的check函数

在JavaScript中&#xff0c;并没有一个内置的名为check的函数。然而&#xff0c;你可以根据需求自定义一个check函数&#xff0c;用于执行各种验证和检查任务。这个check函数的具体作用完全取决于你如何定义和实现它。 以下是一个简单的示例&#xff0c;展示了如何定义一个che…...

赛尼格磁电科技邀您到场参观2024第13届生物发酵展

参展企业介绍 北京赛尼格磁电科技有限公司是一家中加合资的专业永磁组件生产商&#xff0c;2001年成立于中国北京。公司专业从事磁性材料的应用及各类磁系统的设计、开发及制造&#xff0c;公司产品广泛应用于汽车行业、建筑行业、电子行业、航海领域、医学领域、教育领域等。 …...

gpt国内怎么用?最新版本来了

claude 3 opus面世后&#xff0c;这几天已经有许多应用&#xff0c;而其精确以及从不偷懒&#xff08;截止到2024年3月11日还没有偷懒&#xff09;的个性&#xff0c;也使得我们可以用它来首次完成各种需要多轮对话的尝试。 今天我们想要进行的一项尝试就是—— 如何从一个不知…...

Vim脚本语言入门:打造你的编辑器

简介 Vim脚本语言是Vim编辑器内置的一种脚本语言&#xff0c;它赋予用户高度的定制和自动化编辑任务的能力。通过编写Vim脚本&#xff0c;用户可以根据自己的需求来扩展和改进Vim编辑器的功能&#xff0c;从而提高编辑效率和舒适度。 在Vim中&#xff0c;脚本语言被广泛用于创…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...

aardio 自动识别验证码输入

技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”&#xff0c;于是尝试整合图像识别与网页自动化技术&#xff0c;完成了这套模拟登录流程。核心思路是&#xff1a;截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...