题目描述

给定两个以升序排列的整数数组 nums1 和 nums2，以及一个整数 k。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk)。

例如：nums1 = [1,7,11]，nums2 = [2,4,6]，k = 3，输出 [[1,2],[1,4],[1,6]]。

解释：和最小的三对依次是 (1,2) 和=3，(1,4) 和=5，(1,6) 和=7。

解题思路

暴力法

枚举所有 m * n 个数对，排序后取前 k 个。时间复杂度 O(mn log(mn))。当数组较大时效率很低。

最小堆优化（O(k log k)）

核心思想：利用两个数组升序排列的性质，使用最小堆来”多路归并”。

关键观察

对于固定 nums1[i]，它与 nums2 中元素配对的和是递增的：

1
2
3
4
(i,0): nums1[i] + nums2[0]  （最小）
(i,1): nums1[i] + nums2[1]
(i,2): nums1[i] + nums2[2]
...

这类似于合并 k 个有序链表。

算法步骤

  1. 初始化堆：将每行的最小值放入最小堆，即对于 i = 0..min(nums1.length, k)-1，将 (nums1[i] + nums2[0], i, 0) 插入堆中。堆按”和”从小到大排序。

  2. 贪心选取：循环 k 次（或直到堆空）：

    • 弹出堆顶元素 (sum, i, j)，这就是当前最小的数对。
    • 将 (nums1[i], nums2[j]) 加入结果集。
    • 如果 j + 1 < nums2.length，将下一列的元素 (nums1[i] + nums2[j+1], i, j+1) 插入堆中（按行指针后移）。

  3. 返回结果集。

示例说明

以 nums1 = [1,7,11]，nums2 = [2,4,6]，k = 3 为例：

初始化堆：插入 (1+2=3, i=0, j=0), (7+2=9, i=1, j=0), (11+2=13, i=2, j=0) → 堆：[3, 9, 13]

  • 第 1 轮：弹出 (3,0,0)，加入 [1,2]；插入 (1+4=5, 0, 1) → 堆：[5, 9, 13]
  • 第 2 轮：弹出 (5,0,1)，加入 [1,4]；插入 (1+6=7, 0, 2) → 堆：[7, 9, 13]
  • 第 3 轮：弹出 (7,0,2)，加入 [1,6]。k 轮完成。
  • 结果：[[1,2],[1,4],[1,6]]

为什么高效？

对于一个加法表，我们只需要维护最多 min(m, k) 行的最小值。每次弹出一个元素，只向堆中插入该行的下一个元素。总的时间复杂度为 O(k log min(m, k))，远优于 O(mn log(mn))。

复杂度分析

  • 时间复杂度：O(k log min(m, k))，其中 m = nums1.length。每次堆操作 O(log m)，共 k 次。
  • 空间复杂度：O(min(m, k))，堆中最多存储 min(m, k) 个元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package lcr.J061;

import datastructure.MyMinHeap;
import java.util.*;

class Node implements Comparable<Node> {
    int sum; int i; int j;
    public Node(int sum, int i, int j) { this.sum = sum; this.i = i; this.j = j; }
    @Override
    public int compareTo(Node other) { return Integer.compare(this.sum, other.sum); }
}

public class J061 {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> result = new ArrayList<>();
        int heapCap = Math.min(nums1.length, k);
        MyMinHeap<Node> minHeap = new MyMinHeap<>(heapCap);
        for (int i = 0; i < heapCap; i++) {
            minHeap.insert(new Node(nums1[i] + nums2[0], i, 0));
        }
        while (k > 0 && !minHeap.isEmpty()) {
            Node cur = minHeap.extractMin();
            List<Integer> pair = new ArrayList<>();
            pair.add(nums1[cur.i]);
            pair.add(nums2[cur.j]);
            result.add(pair);
            k--;
            if (cur.j + 1 < nums2.length) {
                minHeap.insert(new Node(nums1[cur.i] + nums2[cur.j + 1], cur.i, cur.j + 1));
            }
        }
        return result;
    }
}