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、世官制 是西周时人们仍保持着牢固的宗族血缘联系,人群基本以族区分,并得到宗法封建制的制度上的保证,从而自然形成了各级宗族长同时也就是各级官长,家国一体、家国同构的统治模式、格局。换句话来讲就是我们所说的世袭制。 其…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

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

如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...

高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...