LC-1439. 有序矩阵中的第 k 个最小数组和(二分答案、多路归并)
1439. 有序矩阵中的第 k 个最小数组和
难度困难120
给你一个 m * n
的矩阵 mat
,以及一个整数 k
,矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。
示例 1:
输入:mat = [[1,3,11],[2,4,6]], k = 5
输出:7
解释:从每一行中选出一个元素,前 k 个和最小的数组分别是:
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。
示例 2:
输入:mat = [[1,3,11],[2,4,6]], k = 9
输出:17
示例 3:
输入:mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出:9
解释:从每一行中选出一个元素,前 k 个和最小的数组分别是:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。
示例 4:
输入:mat = [[1,1,10],[2,2,9]], k = 7
输出:12
提示:
m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i]
是一个非递减数组
二分查找解决第k小问题
https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/solution/by-lfool-w2ul/
719. 找出第 K 小的数对距离
1439. 有序矩阵中的第 k 个最小数组和
我们先明确一下原问题:「返回所有可能数组中的第 k 个最小数组和」
对于一个给定的数组和 sum
,如果该数组和小了,那我们就「向右收缩」;如果该数组和大了,那我们就「向左收缩」;如果该数组和满足要求,那我们能不能找一个更小的且满足要求的数组和,所以需要继续「向左收缩」(是不是很像「寻找最左相等元素」?自信点,就是「寻找最左相等元素」)
所以「搜索对象」是什么??很明显就是「数组和」嘛!!
那「搜索范围」又是什么呢??
- 数组和最小值可以到达多少?肯定是该矩形的第一列组成的组数和嘛 (矩形每行递增)
- 数组和最大值可以到达多少?肯定是该矩形的最后一列组成的组数和嘛 (矩形每行递增)
明确了「搜索对象」和「搜索范围」,我们还需要搞清楚怎么确定数组和小了还是大了,肯定要有一个参考对象才能确定近还是远嘛
很聪明,这个参考对象就是题目给的「第 k
最小」。对于数组和 sum
,小于等于该数组和的数量为 n
,如果 n < k
说明数组和小了;如果 n > k
说明数组和大了
class Solution {// https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/solution/by-lfool-w2ul/int m, n, k;int[][] mat;int cnt = 0; // 计算小于等于当前数组和的数量public int kthSmallest(int[][] mat, int k) {this.k = k;this.mat = mat;m = mat.length;n = mat[0].length;// 搜索范围int left = 0, right = 0;for (int i = 0; i < m; i++) {left += mat[i][0];right += mat[i][n - 1];}// 把最小值设为初始值int init = left;while (left <= right) {int mid = left - (left - right) / 2;// 初始值也算一个可行解cnt = 1;dfs(0, init, mid);// 对应数组和大了,向左收缩if (cnt >= k) right = mid - 1;// 对应数组和小了,向右收缩else left = mid + 1;}return left;}// DFS 计算 小于等于 target 的数量private void dfs(int row, int sum, int target) {// 特殊情况,直接返回// sum > target:当前数组和大于 target// cnt > k:当前小于等于 target 的数量大于 k// row >= m:已经到达最后一行 (结束条件)if (sum > target || cnt > k || row >= m) return;// 不做交换dfs(row + 1, sum, target);// 分别与 [1, n-1] 交换for (int i = 1; i < n; i++) {// 更新数组和:减去「第一个元素」,加上「要交换的元素」int newSum = sum - mat[row][0] + mat[row][i];// 交换后的数组和大于 target,直接跳出循环// 原因:由于每行元素递增,所以当前元素大了,该行后面的元素肯定也大了if (newSum > target) break;// 满足要求,cnt + 1cnt++;// 搜索下一行dfs(row + 1, newSum, target);}}
}
多路归并
题解:https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/solution/by-lfool-z9n4/
class Solution {// 对于每次弹出队顶元素后,需要把 n 个元素入队public int kthSmallest(int[][] mat, int k) {int m = mat.length, n = mat[0].length;Set<String> set = new HashSet<>();// 构造一个最小堆PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[m] - b[m]);// init[0..m-1] 存储矩阵的一列元素的下标// init[m]存储该列的和int[] init = new int[m+1];for(int i = 0; i < m; i++){init[m] += mat[i][0];init[i] = 0;}q.offer(init);set.add(Arrays.toString(init));while(k-- > 0){int[] cur = q.poll();if(k == 0) return cur[m];// 构造处需要加入堆的元素,一共m个for(int i = 0; i < m; i++){int[] tmp = (int[])Arrays.copyOf(cur, m+1);if(tmp[i] + 1 >= n)continue; // 下标越界了tmp[m] += mat[i][tmp[i] + 1] - mat[i][tmp[i]]; // 下标i往前进,tmp[m]处增加上变化量tmp[i] += 1;String s = Arrays.toString(tmp);if(set.contains(s)) continue;q.offer(tmp);set.add(s);}}return -1;}
}
多路归并练习题
264. 丑数 II
313. 超级丑数
373. 查找和最小的 K 对数字
786. 第 K 个最小的素数分数
1508. 子数组和排序后的区间和
719. 找出第 K 小的数对距离
1439. 有序矩阵中的第 k 个最小数组和
相关文章:
LC-1439. 有序矩阵中的第 k 个最小数组和(二分答案、多路归并)
1439. 有序矩阵中的第 k 个最小数组和 难度困难120 给你一个 m * n 的矩阵 mat,以及一个整数 k ,矩阵中的每一行都以非递减的顺序排列。 你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。 示例 1:…...

一文1000字从0到1实现Jenkins+Allure+Pytest的持续集成
一、配置 allure 环境变量 1、下载 allure是一个命令行工具,可以去 github 下载最新版:https://github.com/allure-framework/allure2/releases 2、解压到本地 3、配置环境变量 复制路径如:F:\allure-2.13.7\bin 环境变量、Path、添加 F:\…...
给一个有序数组生成平衡搜索二叉树(java)
给一个有序数组生成平衡搜索二叉树 给一个有序数组生成平衡搜索二叉树递归生成二叉树专题 给一个有序数组生成平衡搜索二叉树 给定一个有序的数组,用这个数组生成一个平衡搜索二叉树. 这个题还是很简单的,知道什么时平衡搜索二叉树就行了, 左边值小于头节点值,头节点值小于右边…...

【JavaSE】Java基础语法(二十二):包装类
文章目录 1. 基本类型包装类2. Integer类3. 自动拆箱和自动装箱4. int和String类型的相互转换 1. 基本类型包装类 基本类型包装类的作用 将基本数据类型封装成对象的好处在于可以在对象中定义更多的功能方法操作该数据常用的操作之一:用于基本数据类型与字符串之间的…...

javascript基础十八:说说你对JavaScript中事件循环的理解
一、是什么 JavaScript 在设计之初便是单线程,即指程序运行时,只有一个线程存在,同一时间只能做一件事 为什么要这么设计,跟JavaScript的应用场景有关 JavaScript 初期作为一门浏览器脚本语言,通常用于操作 DOM &#…...

详解js中的浅拷贝与深拷贝
详解js中的浅拷贝与深拷贝 1、前言1.1 栈(stack)和堆(heap)1.2 基本数据类型和引用数据类型1.2.1 概念1.2.2 区别1.2.3 基本类型赋值方式1.2.4 引用类型赋值方式 2、浅拷贝2.1 概念2.2 常见的浅拷贝方法2.2.1 Object.assign()2.2.…...
Day9 敏捷测试——敏捷开发的特征、什么是敏捷测试?、极限编程、极限测试
Day9 敏捷测试——敏捷开发的特征、什么是敏捷测试?、极限编程、极限测试 文章目录 Day9 敏捷测试——敏捷开发的特征、什么是敏捷测试?、极限编程、极限测试敏捷开发的特征1、迭代式开发2、增量交付3、及时反馈4、持续集成5、自我管理敏捷开发和迭代式开发的根本区别1、性质…...

k8s 维护node与驱逐pod
1.维护node节点 设置节点状态为不可调度状态,执行以下命令后,节点状态会多出一个SchedulingDisabled的状态,即新建的pod不会往该节点上调度,本身存在node中的pod保持正常运行 kubectl cordon k8s-node01 kubectl get node 2.驱…...

SouapUI接口测试之创建性能测试
SouapUI也是一个能生动的体现一个系统(项目)性能状态的工具,本篇就来说说如何在SouapUI工具下创建性能测试 一、创建测试用例 由于在《SouapUI接口测试之使用Excel进行参数化》篇已经创建好了测试用例,本篇就不讲解如何创建测试…...

springboot整合kafka入门
kafka基本概念 producer: 生产者,负责发布消息到kafka cluster(kafka集群)中。生产者可以是web前端产生的page view,或者是服务器日志,系统CPU、memory等。 consumer: 消费者,每个consumer属于一个特定的c…...
Rust 笔记:Rust 语言中的字符串
Rust 笔记 Rust 语言中的字符串 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263?spm1001.2101.3001.5343 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq_28550263/article/detail…...
华为OD机试真题 Java 实现【将真分数分解为埃及分数】【牛客练习题】
一、题目描述 分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数,叫做真分数),请将该分数分解为埃及分数。如:8/11 = 1/2+1/5+1/55+1/110。 注:真分数指分子小于分母的分数,分子和分母有可能gcd不为1! 如有多个解,请输出任意一个。 二、输入描述 输…...

Zemax Lumerical | 二维光栅出瞳扩展系统优化
简介 本文提出并演示了一种以二维光栅耦出的光瞳扩展(EPE)系统优化和公差分析的仿真方法。 在这个工作流程中,我们将使用3个软件进行不同的工作 ,以实现优化系统的大目标。首先,我们使用 Lumerical 构建光栅模型并使用…...
Linux-0.11 文件系统read_write.c详解
Linux-0.11 文件系统read_write.c详解 模块简介 该模块实现了文件系统通用的读写的方法read/write/lseek。 根据文件类型的不同,在内部将调用不同的方法。如果是管道文件,则调用pipe.c中的读写方法,如果是字符设备,则会调用cha…...
什么是用户态和内核态?用户态切换内核态会有什么影响?
一、什么是用户态和内核态? 简单来讲,像使用java开发时,调用java中封装的普通方法程序时属于用户态,而操作内存或者cpu比如 new Thread()创建一个线程,Class.forName(xxx.class)这种属于内核态 用户态和内核态是操作系…...

探索iOS之CoreImage框架
CoreImage提供图像处理、人脸识别、图像增强、图像滤镜、图像转场。它操作的数据来自Core Graphics、Core Video、Image IO,使用CPU或GPU进行渲染。CoreImage对底层实现进行封装,为上层提供简单易用的API。 一、CoreImage框架 CoreImage框架分为&#…...
qml 使用Shape 画图形
最近在做项目的时候想这实现一个能够根据相对位置动态改变大小的进度条提示框,偶尔发现了一个很有用的组件Shape这个控件里面可以画各种线条,实线虚线矩形三角形圆角的三角形或者各种自定义形状。下面提供一个2条虚线加上一个矩形的小栗子。更多的自定义形状还是请自…...

MySQL数据库修改root账户密码
博主今天登录数据库遇到了一个问题,通过这篇文章(http://t.csdn.cn/58ECT)解决了。文中关于修改root账户密码的部分,博主觉得有必要写一篇文章总结下。 第一步:用管理员账户打开CMD 第二步:开启mysql服务 …...

基于springboot+Vue+ Element-Plus+mysql实现学生宿舍管理系统
基于springbootVue Element-Plusmysql实现学生宿舍管理系统 一、系统介绍二、功能展示1.登陆2、主页--学生3、主页--宿舍管理员4.学生管理--管理员5.宿管信息--管理员6.宿舍管理--管理员7.信息管理--管理员8.申请管理--管理员9.访客管理--管理员10.水电费管理--管理员11.卫生管…...
中国人才选拔制度演变
1、世官制 是西周时人们仍保持着牢固的宗族血缘联系,人群基本以族区分,并得到宗法封建制的制度上的保证,从而自然形成了各级宗族长同时也就是各级官长,家国一体、家国同构的统治模式、格局。换句话来讲就是我们所说的世袭制。 其…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

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