LeetCode <heap>373. Find K Pairs with Smallest Sums

原创

大学里的混子

修改于 2018-11-16 11:06:31

5570

修改于 2018-11-16 11:06:31

文章被收录于专栏：LeetCodeLeetCode

373. Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.

Example 1:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]] 
Explanation: The first 3 pairs are returned from the sequence: 
             [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

Example 2:

Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [1,1],[1,1]
Explanation: The first 2 pairs are returned from the sequence: 
             [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [1,3],[2,3]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]

题目大意：给两个数组，找出两两组合之和最小的前k个组合。

思路：解决最小或或者最大的k个对象的问题，最直观的就是采用最小堆或者是最大堆，堆又称为优先队列。

java中提供PriorityQueue<>类，可以很好的调用，注意如何自定义顺序。

解法：

第一方法：

      PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[0]+o1[1] - o2[0]-o2[1];
            }
        });

第二种方法：

      Comparator comparator = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                int[] arr1 = (int[])o1;
                int sum1 = arr1[0]+ arr1[1];
                int[] arr2 = (int[])o2;
                int sum2 = arr2[0]+ arr2[1];
                return sum1-sum2;
            }
        };

        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(k,comparator);

两种方法类似，但是第二种方法需要类型强转，写起来较为麻烦。

下面是具体的解法：

     public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<int[]> res = new ArrayList<>();
        if (k<0||(k>0&&(nums1.length==0||nums2.length==0))) return res;
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(k,new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
               //返回是正数，建立最小堆
                return o1[0]+o1[1] - o2[0]-o2[1];
            }
        });
        for (int i = 0;i<nums1.length;i++){
            for (int j = 0;j<nums2.length;j++){
                priorityQueue.add(new int[]{nums1[i],nums2[j]});
            }
        }

        for (int i = 0;i<k&&!priorityQueue.isEmpty();i++) {
            res.add(priorityQueue.remove());
        }
        return res;
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

登录后参与评论

0 条评论

热度