LeetCode 373题 “Find K Pairs with Smallest Sums” 是一个中等难度的题目，要求我们从两个整数数组中找到和最小的k对数字。具体描述如下：

题目描述

给定两个以升序排列的整数数组 nums1 和 nums2，以及一个整数 k。你需要找到和最小的 k 对数字（u1,v1），（u2,v2）…，其中 u1 来自 nums1，v1 来自 nums2。

示例

输入:

nums1 = [1,7,11] nums2 = [2,4,6] k = 3

输出:

[[1,2],[1,4],[1,6]]

解释: 返回序列中的前 3 对数分别是：

• [1,2]，[1,4]，[1,6] 的和分别是 3，5，7，是最小的。

方法一：最小堆（优先队列）

我们可以使用最小堆来解决这个问题。具体步骤如下：

1. 初始化最小堆：
   • 将 nums1 中的每个元素与 nums2 中的第一个元素的组合放入最小堆中。堆中的元素是一个三元组 (sum, i, j)，其中 sum = nums1[i] + nums2[j]，i 和 j 分别是 nums1 和 nums2 中的索引。
2. 提取最小元素并扩展：
   • 每次从堆中提取最小元素 (sum, i, j)，将其加入结果列表。
   • 如果 j < nums2.length - 1，将新的组合 (nums1[i] + nums2[j+1], i, j+1) 加入堆中。
3. 重复步骤2直到找到k对。

代码实现（Python）

import heapq

min_heap = []
# 初始化堆
for i in range(min(k, len(nums1))):  # 只需要前k个元素，如果nums1长度大于k
    heapq.heappush(min_heap, (nums1[i] + nums2[0], i, 0))

result = []
while k > 0 and min_heap:
    current_sum, i, j = heapq.heappop(min_heap)
    result.append([nums1[i], nums2[j]])
    if j + 1 < len(nums2):
        heapq.heappush(min_heap, (nums1[i] + nums2[j+1], i, j+1))
    k -= 1

return result

nums1 = [1,7,11] nums2 = [2,4,6] k = 3 print(kSmallestPairs(nums1, nums2, k)) # 输出: [[1,2],[1,4],[1,6]]

复杂度分析

• 时间复杂度：O(k * log(min(k, m)))，其中 m 是 nums1 的长度。每次从堆中提取最小元素的时间复杂度为 O(log(min(k, m)))，最多进行 k 次。
• 空间复杂度：O(min(k, m))，堆的大小最多为 min(k, m)。

其他方法

除了最小堆，还可以考虑使用二分查找 + 双指针的方法，但实现起来相对复杂，且在某些情况下效率不如最小堆。

总结

使用最小堆的方法可以高效地解决此问题，通过维护一个大小为 min(k, m) 的堆，确保每次都能找到当前最小的组合，逐步构建结果列表。这种方法在处理大规模数据时表现良好，且实现相对简单。

希望这个详细的解答能帮助你理解并解决这个题目！如果有任何进一步的问题，欢迎继续提问。