LeetCode LCR 061. 查找和最小的 K 对数字
目录
题目描述
题意分析
给两个升序数组
nums1与nums2，从两边各取一个数组成数对，要求返回和最小的 $k$ 个数对。数对总数是 $m \times n$，而 $k$ 只到 $10^4$，所以要的是「前 $k$ 小」，不是全体排序。「两个数组都已经升序」是最关键的信号。它意味着固定左边下标
i之后，随着右边下标j增大，数对的和单调不降；也就是说 $m$ 行候选各自天然有序，问题的形状是「从 $m$ 条有序序列里取出全局前 $k$ 小」。约束里 $m, n$ 可达 $10^5$，$m \times n$ 高达 $10^{10}$，任何把所有数对枚举出来的做法都不可行，这条约束直接排除了「全枚举再排序」。返回值只要求这 $k$ 个数对本身，题目允许 $k$ 大于数对总数，此时把能凑出来的全部返回即可，不是错误输入。
边界上要注意三处：$k$ 大于 $m \times n$ 时结果长度小于 $k$，不能死循环等待凑满；数组元素取值范围到 $10^9$，两数之和最大 $2 \times 10^9$ 已经超出 32 位有符号整数，比较时必须防溢出；两个数组都可能含重复值，重复数对是合法结果，不能去重。
解法：堆维护最优候选
核心思路
暴力做法是二重循环枚举所有 $m \times n$ 个数对，全部排序后取前 $k$ 个。逻辑正确，但在 $m = n = 10^5$ 时要生成 $10^{10}$ 个数对，无论时间还是内存都不可能。
瓶颈在于暴力把「找前 $k$ 小」做成了「先算出全部再挑」，而绝大多数数对根本没有资格进入答案：如果数对 $(i, j)$ 已经不在前 $k$ 小之内，那么 $(i, j+1)$、$(i, j+2)$ 这些和更大的数对更不可能在，却仍然被枚举了一遍。
观察到有序性带来的偏序结构：
nums1[i] + nums2[j] <= nums1[i] + nums2[j+1]，所以第i行的数对按j递增就是一条有序链；同理列方向也有序。把每一行看成一条已排好序的链，问题就是标准的多路归并——从 $m$ 条有序链里依次取出全局最小的元素，取 $k$ 次。于是维护一个小根堆，堆中存的是下标对
(i, j)，比较依据是nums1[i] + nums2[j]。初始时把每一行的行首(i, 0)放进堆，行数超过 $k$ 的部分不必放，因为答案最多只有 $k$ 个元素，第 $k+1$ 行的行首即使最小也不可能挤进前 $k$（它前面至少有前 $k$ 行的行首比它小或相等）。这个过程维持的不变量是：堆中永远包含「所有尚未被取出、但其同行前驱已被取出」的数对。换句话说，每一行至多有一个代表在堆里，且这个代表是该行剩余元素中最小的那个。因此堆顶就是全局尚未取出的最小数对。每弹出一个
(i, j)，就把同一行的后继(i, j+1)补进堆，让第i行重新有代表；补进去之前要检查j+1 < n，行尾没有后继。重复 $k$ 次，弹出顺序即为和从小到大的前 $k$ 个数对。
解题步骤
- 建一个以
nums1[i] + nums2[j]为序的小根堆，堆里放下标对而不是数值本身。放下标是因为弹出后还要知道「同一行的下一个是谁」，只存数值就丢失了位置信息，无法生成后继。- 把
(0, 0), (1, 0), ..., (min(m, k) - 1, 0)依次入堆。只取前 $\min(m, k)$ 行是剪枝：答案长度不超过 $k$，第 $k$ 行之后的行首永远排不进前 $k$ 名，入堆纯属浪费。- 循环执行「弹出堆顶、记入答案」，直到答案凑满 $k$ 个或者堆为空。堆空的判断不能省，$k$ 大于数对总数时正是靠它退出。
- 每次弹出
(i, j)后，若j + 1 < n则把(i, j + 1)入堆。只补同行后继、不补下一行的(i+1, j)，是因为每一行的行首在初始化时就已经全部入堆，补列方向会造成同一数对被重复加入。- 比较两个数对的和时用 64 位运算。两个 $10^9$ 相加会溢出 32 位有符号整数，溢出后变成负数，堆序会彻底错乱。
以
nums1 = [1, 7, 11]、nums2 = [2, 4, 6]、k = 3走一遍：初始化时 $\min(3, 3) = 3$ 行的行首全部入堆，即(0,0)和 1+2=3、(1,0)和 7+2=9、(2,0)和 11+2=13。第一次弹出堆顶(0,0)，答案记[1,2]；j+1 = 1 < 3，把(0,1)和 1+4=5 入堆，堆内是 5、9、13。第二次弹出(0,1)，答案记[1,4]；补入(0,2)和 1+6=7，堆内是 7、9、13。第三次弹出(0,2)，答案记[1,6]；j+1 = 3已到行尾，不补。此时答案已有 3 个，循环结束，返回[[1,2],[1,4],[1,6]]。可以看到堆始终只有三个元素、每行至多一个代表，整个过程从未碰过7和11那两行的第二个元素。
代码实现
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> ans = new ArrayList<>();
PriorityQueue<int[]> pq = new PriorityQueue<>(
(a, b) -> Long.compare((long) nums1[a[0]] + nums2[a[1]], (long) nums1[b[0]] + nums2[b[1]]));
for (int i = 0; i < nums1.length && i < k; i++) {
pq.offer(new int[] {i, 0});
}
while (!pq.isEmpty() && ans.size() < k) {
int[] cur = pq.poll();
ans.add(List.of(nums1[cur[0]], nums2[cur[1]]));
if (cur[1] + 1 < nums2.length) {
pq.offer(new int[] {cur[0], cur[1] + 1});
}
}
return ans;
}
}
type pairHeap struct {
nums1 []int
nums2 []int
idx [][2]int
}
func (h pairHeap) Len() int { return len(h.idx) }
func (h pairHeap) Less(i, j int) bool {
a, b := h.idx[i], h.idx[j]
return h.nums1[a[0]]+h.nums2[a[1]] < h.nums1[b[0]]+h.nums2[b[1]]
}
func (h pairHeap) Swap(i, j int) { h.idx[i], h.idx[j] = h.idx[j], h.idx[i] }
func (h *pairHeap) Push(x any) { h.idx = append(h.idx, x.([2]int)) }
func (h *pairHeap) Pop() any {
n := len(h.idx)
v := h.idx[n-1]
h.idx = h.idx[:n-1]
return v
}
func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
h := &pairHeap{nums1: nums1, nums2: nums2}
for i := 0; i < len(nums1) && i < k; i++ {
h.idx = append(h.idx, [2]int{i, 0})
}
heap.Init(h)
ans := make([][]int, 0, k)
for h.Len() > 0 && len(ans) < k {
cur := heap.Pop(h).([2]int)
ans = append(ans, []int{nums1[cur[0]], nums2[cur[1]]})
if cur[1]+1 < len(nums2) {
heap.Push(h, [2]int{cur[0], cur[1] + 1})
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(k \log k)$，堆内元素数始终不超过 $\min(m, k)$，初始化入堆 $\min(m, k)$ 次、主循环最多弹出并补入各 $k$ 次，每次堆操作 $O(\log k)$。
- 空间复杂度：$O(\min(m, k))$，堆中每行至多存一个下标对，与答案数组分开计算；答案本身的 $O(k)$ 是必须的输出开销。
关键点总结
- 多个有序序列求全局前 $k$ 小，标准形态就是「行首入堆 + 弹一个补一个同行后继」。识别出「固定一维后另一维单调」这个结构，比记住模板更重要。
- 堆里存下标而不是存值。下标携带位置信息，弹出后才知道后继是谁；存值会让后继无从生成，是这类题最常见的设计失误。
- 只补同行后继、不补跨行邻居，配合「初始化把所有行首入堆」，恰好保证每个数对被且仅被加入一次，不需要额外的访问标记去重。
- 初始入堆时用 $\min(m, k)$ 截断，是把堆规模从 $O(m)$ 压到 $O(k)$ 的关键剪枝，在 $m$ 远大于 $k$ 时决定成败。
- 面试视角：先说暴力 $O(mn \log(mn))$ 并指出规模不可行，再讲有序性带来的偏序结构，最后落到堆。直接甩出堆的代码，容易被追问「为什么不会重复」而卡住。
- 面试视角：常见追问是「能否做到 $O(k)$ 或更优」。可以答用「二分答案 + 计数」把和的阈值二分出来，达到 $O((m + n) \log(\max - \min))$ 级别，思路与 378、719 同源，能顺势串起整条题链。
易错点总结
- 错误写法：比较器写成
(nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]])的int相减。用例nums1 = [1000000000, 1000000000]、nums2 = [1000000000, 1000000000]→ 两数之和 $2 \times 10^9$ 已溢出int，相减再次溢出，堆序错乱，输出的数对顺序错误。- 错误写法：初始化时把所有 $m$ 行的行首都入堆，不用 $k$ 截断。用例
m = 100000、k = 1→ 堆规模被撑到 $10^5$，初始化就花掉 $O(m \log m)$，在极端数据下超时。- 错误写法：弹出
(i, j)后既补(i, j+1)又补(i+1, j)。用例nums1 = [1, 1]、nums2 = [1, 1]、k = 4→ 数对(1, 1)会分别从(0,1)和(1,0)被加入两次，答案里出现重复项且漏掉别的数对。- 错误写法：补后继时忘记判断
j + 1 < n。用例nums1 = [1, 2]、nums2 = [3]、k = 3→ 弹出(0,0)后访问nums2[1]，下标越界抛异常。- 错误写法：主循环只写
ans.size() < k不判堆空。用例nums1 = [1]、nums2 = [2]、k = 10→ 堆在第二轮就空了，继续poll得到null并抛空指针异常，正确行为是返回仅有的一个数对。- 错误写法：把弹出的数对按值去重，认为重复数对是脏数据。用例
nums1 = [1, 1]、nums2 = [1, 2]、k = 2→ 去重后只剩[1,1]一项，而正确答案是[[1,1],[1,1]]，两个1来自不同下标，是两个合法数对。- 错误写法：堆里存
List.of(nums1[i], nums2[j])这样的数值对，弹出后靠数值反查下标。用例nums1 = [1, 1, 1]、nums2 = [1, 2, 3]、k = 3→ 数值1在nums1中出现三次，无法确定弹出的是哪一行，后继补错，结果缺项。- 错误写法：用大根堆维护规模为 $k$ 的窗口，把全部 $m \times n$ 个数对都
offer一遍再取。用例m = n = 100000→ 循环次数 $10^{10}$，必然超时，堆的作用被浪费在了「筛」而不是「导航」上。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 373. 查找和最小的 K 对数字 | 中等 | 与本题同题，可用来对照堆导航与二分答案两种实现 |
| 378. 有序矩阵中第 K 小的元素 | 中等 | 有序链由矩阵的行直接给出，且只要第 $k$ 个而非前 $k$ 个 |
| 786. 第 K 个最小的质数分数 | 中等 | 比较键是分数需避免浮点误差，行内单调方向与本题相反 |
| 632. 最小区间 | 困难 | 同样是 $k$ 路指针推进，但目标从取前 $k$ 小变成维护覆盖区间 |
| 719. 找出第 K 小的数对距离 | 困难 | 数对规模更大，必须改用二分答案配合双指针计数 |
| 23. 合并 K 个升序链表 | 困难 | 多路归并的链表形态，要取完全部元素而不是前 $k$ 个 |
| LCR 060. 前 K 个高频元素 | 中等 | 排序键换成频次，堆的用法是筛前 $k$ 名而非按序导航 |