贵州网站集约化建设,许昌网站制作公司,wordpress手机电影,河东网站建设1439. 有序矩阵中的第 k 个最小数组和
难度困难120
给你一个 m * n 的矩阵 mat#xff0c;以及一个整数 k #xff0c;矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。
示例 1#xff1a;…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.lengthn mat.length[i]1 m, n 401 k min(200, n ^ m)1 mat[i][j] 5000mat[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;SetString set new HashSet();// 构造一个最小堆PriorityQueueint[] q new PriorityQueue((a, b) - a[m] - b[m]);// init[0..m-1] 存储矩阵的一列元素的下标// init[m]存储该列的和int[] init new int[m1];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, m1);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 个最小数组和
