再来做一下373，之前都没有试过用小顶堆求第K小的，有序这个条件对我而言是摆设了
查找和最小的 K 对数字【LC373】
给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
大顶堆
class Solution { public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[0] + o2[1] - o1[0] -o1[1]); List<List<Integer>> res = new ArrayList<>(); int n = nums1.length, m = nums2.length; for (int i = 0; i < Math.min(k, n); i++){ for (int j = 0; j < Math.min(k, m); j++){ int[] n1 = new int[]{nums1[i], nums2[j]}; if (pq.size() < k){ pq.add(n1); }else if(pq.size() == k && n1[0] + n1[1] < pq.peek()[0] + pq.peek()[1]){ pq.poll(); pq.add(n1); } } } while(!pq.isEmpty()){ int[] poll = pq.poll(); res.add(Arrays.asList(poll[0], poll[1])); } return res; } }
实现
class Solution { public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { int n = nums1.length, m = nums2.length; var ans = new ArrayList<List<Integer>>(k); // 预分配空间 var pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]); for (int i = 0; i < Math.min(n, k); i++) // 至多 k 个 pq.add(new int[]{nums1[i] + nums2[0], i, 0}); while (!pq.isEmpty() && ans.size() < k) { var p = pq.poll(); int i = p[1], j = p[2]; ans.add(List.of(nums1[i], nums2[j])); if (j + 1 < m) pq.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1}); } return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/solutions/2286318/jiang-qing-chu-wei-shi-yao-yi-kai-shi-ya-i0dj/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution { public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { int n = nums1.length, m = nums2.length; var ans = new ArrayList<List<Integer>>(k); // 预分配空间 var pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]); pq.add(new int[]{nums1[0] + nums2[0], 0, 0}); while (!pq.isEmpty() && ans.size() < k) { var p = pq.poll(); int i = p[1], j = p[2]; ans.add(List.of(nums1[i], nums2[j])); if (j == 0 && i + 1 < n) pq.add(new int[]{nums1[i + 1] + nums2[0], i + 1, 0}); if (j + 1 < m) pq.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1}); } return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/solutions/2286318/jiang-qing-chu-wei-shi-yao-yi-kai-shi-ya-i0dj/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
有序矩阵中的第 k 个最小数组和【LC1439】
给你一个
m * n的矩阵mat，以及一个整数k，矩阵中的每一行都以非递减的顺序排列。你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。
class Solution { public int kthSmallest(int[][] mat, int k) { // 从m行中每行选取1个元素，每行有n个选择，因此总共方案数为n^m // 我们最终要返回方案和为第k小的和，因此只需要记录选到第i行时，最小的k个和即可，然后进行多路归并，结果一定是在这些组合的基础上添加元素 // 实现：暴力或者小顶堆 int m = mat.length, n = mat[0].length; int[] a = new int[]{0}; for (int[] row : mat){ int[] b = new int[a.length * n]; int i = 0; for (int num1 : a){ for (int num2 : row){ b[i++] = num1 + num2; } } Arrays.sort(b); if (b.length > k){ b = Arrays.copyOfRange(b, 0, k); } a = b; } return a[k - 1]; } }
class Solution { public int kthSmallest(int[][] mat, int k) { var a = new int[]{0}; for (var row : mat) a = kSmallestPairs(row, a, k); return a[k - 1]; } // 373. 查找和最小的 K 对数字 private int[] kSmallestPairs(int[] nums1, int[] nums2, int k) { int n = nums1.length, m = nums2.length, sz = 0; var ans = new int[Math.min(k, n * m)]; var pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]); pq.add(new int[]{nums1[0] + nums2[0], 0, 0}); while (!pq.isEmpty() && sz < k) { var p = pq.poll(); int i = p[1], j = p[2]; ans[sz++] = nums1[i] + nums2[j]; // 数对和 if (j == 0 && i + 1 < n) pq.add(new int[]{nums1[i + 1] + nums2[0], i + 1, 0}); if (j + 1 < m) pq.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1}); } return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/solutions/2286593/san-chong-suan-fa-bao-li-er-fen-da-an-du-k1vd/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
