当前位置： 面试刷题>> 查找和最小的 K 对数字(经典算法150题)
### 题目描述
给定两个已排序的整数数组 `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 示例代码
```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 示例代码
```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 示例代码
```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 的示例实现。