LeetCode刷题——查找和最小的 K 对数字＃373＃Medium

查找和最小的 K 对数字的思路探讨与源码
    查找和最小的 K 对数字的题目如下图，该题属于数组类和队列类型的题目，主要考察对于排序方法的使用和数组结构的理解。本文的题目作者想到2种方法，分别是多路归并方法和优先队列方法，其中多路归并方法使用Java进行编写，而优先队列方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。
    何为多路归并算法？多路归并是外部排序的基础，实现也比较简单，和最简单的归并排序中的二路归并是基本一样的，只不过路数是浮动的k值。算法一般大致分为四个步骤：（1）假设有K路数据流，流内部是有序的，且同为升序或降序。（2）首先读取每个流的第一个数，如果已经遍历结束则直接跳过。（3）将有效的n个数比较，选出最小的那路，输出后继续读取下一个。（4）直到所有K路都已经遍历结束即终止程序。
    本人认为该题目可以多路归并方法的思路进行解决，首先计算数组的长度并初始化列表和队列，将队列进行初值赋予操作。然后开始遍历循环，将队列的队首元素弹出并提取对应值，然后判断标志值是否为真后，将元素对应的数组值加入到列表里，判断下标的下一个值是否到数组的末尾，如果没有到末尾则将下标加入到队列里，直到最终循环结束并返回列表结果。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟
class Solution {
    boolean flag = true;
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int numLen1 = nums1.length;
        int numLen2 = nums2.length;
        if (numLen1 > numLen2 && ! (flag = false)){
            return kSmallestPairs(nums2, nums1, k);
        }
        List<List<Integer>> res = new ArrayList<>();
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->(nums1[a[0]]+nums2[a[1]])-(nums1[b[0]]+nums2[b[1]]));
        for (int ir = 0; ir < Math.min(numLen1, k); ir++){
            queue.add(new int[]{ir, 0});
        } 
        while (res.size() < k && ! queue.isEmpty()) {
            int[] ind = queue.poll();
            int a = ind[0];
            int b = ind[1];
            res.add(new ArrayList<>(){
   {
                add(flag ? nums1[a] : nums2[b]);
                add(flag ? nums2[b] : nums1[a]);
            }});
            if (b + 1 < numLen2){
                queue.add(new int[]{a, b + 1});
            }
        }
        return res;
    }
}

    显然，我们的多路归并方法的效果还不错，同时还可以使用优先队列的方法解决。首先计算两个数组的长度，初始化一个列表并初始化一个队列后赋值。开始循环遍历，将队列中的最小的值弹出并赋值，将其对应的元素加入到列表里，判断下标的下一位是否已经到末尾，如果没有到，则将数组结果和下标加入到堆中，直到最终遍历结束并返回列表。所以按照这个思路就可以解决，下面是Python代码：

#喷火龙与水箭龟
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        numLen1 = len(nums1)
        numLen2 = len(nums2)
        res = []
        queue = [(nums1[ir] + nums2[0], ir, 0) for ir in range(min(k, numLen1))]
        while queue and len(res) < k:
            _, ir, jr = heappop(queue)
            res.append([nums1[ir], nums2[jr]])
            if(jr + 1 < numLen2):
                heappush(queue, (nums1[ir] + nums2[jr + 1], ir, jr + 1))
        return res

    从结果来说Java版本多路归并方法的效率不错，而Python版本的优先队列方法的速度也还可以，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。