企业官网建设流程全解析

LeetCode 373 查找和最小的 K 对数字（Java 可 AC 版）

一、先看清关键陷阱 🎯

题目没明说但很重要：两个数组都是升序的。这是所有优化的前提。

暴力是把
“m×n” 对全生成再排序 →
“O(mn log mn)”，m/n 到 10⁵ 直接爆。

正确姿势：利用矩阵单调性 + 最小堆做 K 路归并。

把
“(i, j)” 看成矩阵：行
“i” 固定时，
“j” 越大和越大；列
“j” 固定时，
“i” 越大和越大。

二、标准解法：最小堆（推荐，面试首选）

核心去重策略（最容易写错的地方）

堆里只推 每行第一个
“(i, 0)”，弹出
“(i, j)” 时再推
“(i, j+1)”。
这样每对
“(i, j)” 只会从它左边那对
“(i, j-1)” 生成一次，天然无重复，不需要
“HashSet”。

代码

class Solution {
public List<List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List> res = new ArrayList<>();
if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0 || k <= 0) {
return res;
}

// 小根堆：按和升序 PriorityQueue<int[]> pq = new PriorityQueue<>( (a, b) -> (nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]]) ); // 每行只入队第一个元素 for (int i = 0; i < Math.min(k, nums1.length); i++) { pq.offer(new int[]{i, 0}); } while (!pq.isEmpty() && k > 0) { int[] cur = pq.poll(); int i = cur[0], j = cur[1]; res.add(Arrays.asList(nums1[i], nums2[j])); k--; // 同一行的下一个 if (j + 1 < nums2.length) { pq.offer(new int[]{i, j + 1}); } } return res; }

}

为什么
“Math.min(k, nums1.length)” 入队就够了？

• 第 0 行最小是
  “nums1[0]+nums2[0]”
• 第 k 行最小是
  “nums1[k]+nums2[0]” ≥ 前 k 个答案的上界
• 多入的行永远轮不到弹出，纯浪费内存

三、复杂度

复杂度
堆最多元素数
“min(k, m)”
每次 poll/offer
“O(log k)”
最多取 k 次
“O(k log k)”
空间
“O(k)”

比暴力
“O(mn)” 在 k≪mn 时快几个数量级。

四、两种常见错误写法（避坑）

❌ 入队所有
“(0,0),(0,1)…(1,0),(1,1)…” → 退化暴力

❌ 用
“HashSet” 去重 → 能过但多
“O(k)” 哈希开销，面试会被追问

✅ 行指针推进法是这道题的「标准答案」。

五、拓展：多路归并视角（帮你和 23. Merge K Sorted Lists 串起来）

把每一行
“nums1[i] + nums2[j]” 看成一个有序链表：

行0: (0,0) → (0,1) → (0,2) → …
行1: (1,0) → (1,1) → (1,2) → …
行2: …

这就是 K 个有序链表取前 k 小，堆里维护每条链当前头节点即可——和本题完全同构。

要不要我顺手给你一版 「二分答案 + 每行双指针」的
“O(m log(range))” 解法？在 k 很大（接近 mn）时反而比堆更稳，很多面试官会追这一问。