Hacker and Geeker's Way

算法是每个程序员的必备技能，而掌握算法的方法除了看书和看视频外，更多的是通过做题来提高算法能力，在众多的在线编程平台中，LeetCode 以其丰富的题库和高质量的题目解析，成为了全球程序员和计算机科学爱好者提升编程技能、准备技术面试的重要平台。在本文中，我们将介绍 LeetCode 上的一道精选题目——373. 查找和最小的 K 对数字，通过这道题目来介绍其高效的解法。

题目描述

373. 查找和最小的 K 对数字

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

示例 1

• 输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
• 输出: [1,2],[1,4],[1,6]
• 解释: 返回序列[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]中的前 3 对数

示例 2

• 输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
• 输出: [1,1],[1,1]
• 解释: 返回序列[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]中的前 2 对数

提示

• 1 <= nums1.length, nums2.length <= 105
• -109 <= nums1[i], nums2[i] <= 109
• nums1 和 nums2 均为升序排列
• 1 <= k <= 104
• k <= nums1.length \* nums2.length

优先队列解法

使用优先队列算法可以很巧妙地解决这道题，我们假设 nums1 是 [1, 7, 11, 16]，nums2 是 [2, 9, 10, 15]，首先根据 nums1 的长度生成 n 个队列，每个队列的元素是 nums1 数组和 nums2 数组组合的值，比如用 nums1 的第 1 个元素1和 nums2 的所有元素进行组合，得到第 1 个队列[1, 2] -> [1, 9] -> [1, 10] -> [1, 15]，用 nums 的第 2 个元素7和 nums2 的所有元素进行组合，得到第 2 个队列[7, 2] -> [7, 9] -> [7, 10] -> [7, 15]，这样依次得到 4 个队列后，我们开始比较每个队列的第 1 个元素，即第 1 列的元素，见下图中红色虚线框的元素：

可以看到第 1 队列的[1, 2]最小，将其从队列弹出并放入结果数组中，然后第 1 队列右边的元素依次左移：

第 1 队列的元素左移完成后，再次比较每个队列的第 1 个元素：

这次是第 2 队列的[7, 2]最小，将其放入结果数组中，然后第 2 队列右边的元素依次左移：

第 2 队列的元素左移完成后，再次比较每个队列的第 1 个元素：

按照这个方法不断地重复进行，最终只要得到 k 个最小元素就能完成题目的要求了。

最小堆解法

另外一种解题思路是利用最小堆进行求解，主要通过构建一个最小堆来存放每次遍历到的对值，我们通过以下示例进行说明。

假设 nums1 是 [1, 7, 11, 16]，nums2 是 [2, 9, 10, 15]，其中 nums1[0]和 nums2[0]的组合是最小的，将其先放到最小堆Heap中，result是存放结果的数组，visited用来记录每次访问过的对值，用来避免最小堆中存放重复的对值，如下图所示：

从Heap中弹出第 1 个对值，将其放到result中，这样我们就得到第 1 个最小对值，然后分别从该对值的两个数组中右移一位，比如 nums1 中的1右移后就是7，nums2 中的2右移后就是9，并与之前的最小对值进行组合，得到 2 个新的对值，分别是(1, 9)和(7, 2)，再将这 2 个对值放到Heap中，因为Heap是最小堆，所以第一个元素是其中最小的对值，也就是(7,2)：

同样地，从Heap中弹出第 1 个对值，也就是(7, 2)，将其放入result中，然后从该对值的两个数组中右移一位，右移后分别是11和9，再将这 2 个数字和该对值进行组合，得到 2 个新的对值，分别是(7, 9)和(11, 2)，将这 2 个对值放到Heap中，现在加上之前的元素，Heap中公有 3 个元素，其中最小元素是(1,9)：

再从Heap中弹出第 1 个对值，也就是(1, 9)，将其放入result中，然后从该对值的两个数组中右移一位，也就是7和10，进行组合后得到 2 个新的对值，分别是(1, 10)和(7, 9)，其中(7, 9)已经在之前访问过了，所以不放到Heap中，这时Heap共有 3 个元素，其中(1, 10)最小：

同样地，从Heap中弹出第 1 个对值，也就是(1, 10)，将其放入result中，其实这个时候已经可以结束了，因为 k 是 4，而在 result 中已经有 4 个对值了，但我们可以看下继续往Heap中添加的值是什么。从对值(1, 10)的两个数组中右移一位，也就是7和15，进行组合后得到 2 个新的对值，分别是(1, 15)和(7, 10)，将他们添加到Heap中后，Heap共有 4 个元素，其中(11, 2)最小。按照这种方式循环获取最小对值，最终就可以获得 k 个最小对值了。

总结

在本文中，我们详细分析了 LeetCode 第373题的两种高效解决方法：优先队列法和最小堆法。这两种方法各有其独特的优势和适用场景，体现了算法解决问题的多样性和灵活性。希望通过本文的介绍，能够帮助大家对这两种方法有更深刻的理解，并在实际编程实践中灵活运用。