题目描述

给定两个已排序的整数数组 nums1 和 nums2，以及一个整数 k，要求找出和最小的 k 对数字对 (i, j)，其中 i 是 nums1 的索引，j 是 nums2 的索引。每对 (i, j) 形成的数字对值为 nums1[i] + nums2[j]。

示例

假设 nums1 = [1, 7, 11]，nums2 = [2, 4, 6]，k = 3，则和最小的 3 对数字对为 (1, 2)，(1, 4)，(1, 6)，它们的和分别为 3，5，7。

解题思路

这个问题可以使用最小堆（优先队列）来解决。我们可以将每对数字对的和以及它们的索引作为元素放入最小堆中，每次从堆中取出和最小的元素，然后更新堆。具体步骤如下：

1. 初始化一个最小堆，堆中的元素包含数字对的和、nums1 的索引和 nums2 的索引。
2. 将第一对 (nums1[0], nums2[0]) 及其和加入堆中。
3. 重复以下步骤 k 次：
   • 从堆中取出和最小的元素（包括和、两个索引）。
   • 将这对数字对的结果输出或存储。
   • 如果 nums1 或 nums2 的索引还可以继续增加（即未到达数组末尾），则将新的数字对（通过增加索引）及其和加入堆中。

PHP 示例代码

class Pair {
    public $sum;
    public $i;
    public $j;

    function __construct($sum, $i, $j) {
        $this->sum = $sum;
        $this->i = $i;
        $this->j = $j;
    }
}

function findKthSmallestPairs($nums1, $nums2, $k) {
    $result = [];
    $heap = new SplPriorityQueue();
    $heap->insert(new Pair($nums1[0] + $nums2[0], 0, 0), -$nums1[0] - $nums2[0]); // 使用负值保证是最小堆

    while (!$heap->isEmpty() && count($result) < $k) {
        $pair = $heap->extract();
        $result[] = [$nums1[$pair->i], $nums2[$pair->j]];

        if ($pair->i + 1 < count($nums1)) {
            $heap->insert(new Pair($nums1[$pair->i + 1] + $nums2[$pair->j], $pair->i + 1, $pair->j), -$nums1[$pair->i + 1] - $nums2[$pair->j]);
        }
        if ($pair->j + 1 < count($nums2)) {
            $heap->insert(new Pair($nums1[$pair->i] + $nums2[$pair->j + 1], $pair->i, $pair->j + 1), -$nums1[$pair->i] - $nums2[$pair->j + 1]);
        }
    }

    return $result;
}

// 示例用法
$nums1 = [1, 7, 11];
$nums2 = [2, 4, 6];
$k = 3;
print_r(findKthSmallestPairs($nums1, $nums2, $k));

Python 示例代码

import heapq

def findKthSmallestPairs(nums1, nums2, k):
    heap = []
    result = []
    if not nums1 or not nums2 or k <= 0:
        return result

    heapq.heappush(heap, (nums1[0] + nums2[0], 0, 0))

    while heap and len(result) < k:
        _, i, j = heapq.heappop(heap)
        result.append((nums1[i], nums2[j]))

        if i + 1 < len(nums1):
            heapq.heappush(heap, (nums1[i + 1] + nums2[j], i + 1, j))
        if j + 1 < len(nums2):
            heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))

    return result

# 示例用法
nums1 = [1, 7, 11]
nums2 = [2, 4, 6]
k = 3
print(findKthSmallestPairs(nums1, nums2, k))

JavaScript 示例代码

class Pair {
    constructor(sum, i, j) {
        this.sum = sum;
        this.i = i;
        this.j = j;
    }
}

function findKthSmallestPairs(nums1, nums2, k) {
    const result = [];
    const heap = [];
    if (!nums1.length || !nums2.length || k <= 0) return result;

    heap.push(new Pair(nums1[0] + nums2[0], 0, 0));
    heap.sort((a, b) => a.sum - b.sum);

    while (heap.length && result.length < k) {
        const [pair] = heap.splice(0, 1);
        result.push([nums1[pair.i], nums2[pair.j]]);

        if (pair.i + 1 < nums1.length) {
            heap.push(new Pair(nums1[pair.i + 1] + nums2[pair.j], pair.i + 1, pair.j));
            heap.sort((a, b) => a.sum - b.sum);
        }
        if (pair.j + 1 < nums2.length) {
            heap.push(new Pair(nums1[pair.i] + nums2[pair.j + 1], pair.i, pair.j + 1));
            heap.sort((a, b) => a.sum - b.sum);
        }
    }

    return result;
}

// 示例用法
const nums1 = [1, 7, 11];
const nums2 = [2, 4, 6];
const k = 3;
console.log(findKthSmallestPairs(nums1, nums2, k));

以上代码均实现了查找和最小的 k 对数字对的功能，并给出了 PHP、Python 和 JavaScript 的示例实现。