LeetCode_Heap_373. Find K Pairs with Smallest Sums 查找和最小的K对数字【堆】【C++/java】【中等】

2021/11/7 11:40:24

编程Tag： get new Java int queue nums1 nums2 pairs sums

本文主要是介绍LeetCode_Heap_373. Find K Pairs with Smallest Sums 查找和最小的K对数字【堆】【C++/java】【中等】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一，题目描述

英文描述

中文描述

示例与说明

二，解题思路

三，AC代码

C++

Java

四，解题过程

第一博

第二搏

第三博

一，题目描述

英文描述

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.

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

中文描述

给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。

示例与说明

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二，解题思路

java版本的代码采用小根堆，暴力双重循环，将所有组合依次放入堆中，最后筛选前k个；

上面的做法会超时，可以对部分条件进行筛选。由于只需要前k个最小组合，每个数组（nums1或nums2）中选出的数字个数不可能超过k（有k个小的不选，选大的？）。这样可以通过目前的测试用例。

C++版本采用大根堆，维持最小的k个组合，堆顶为最小k个组合中最大的一个。

当堆的大小达到k时，判断新组合与堆顶的优先级关系，若堆顶优先级高（说明堆顶的组合大于新组合），则将新组合放入堆中，并弹出堆顶。

三，AC代码

C++

class Solution {
public:
    struct cmp {
        // 大根堆，维持k个最小值，堆顶为最小值中最大的一个
        bool operator()(pair<int, int> a, pair<int, int> b) {
            return (a.first + a.second) < (b.first + b.second);
        }
    };
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<vector<int>> ans;
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> queue;// ！！！
        for (int i = 0; i < nums1.size() && i < k; i++) {
            for (int j = 0; j < nums2.size() && j < k; j++) {
                if (queue.size() < k) {
                    queue.push({nums1[i], nums2[j]});
                } 
                // 当堆顶的优先级大于新的数据时，将其加入到堆中
                // 在这里直观的理解就是新数据小于堆顶，因此允许进入前k小
                else if (cmp()({nums1[i], nums2[j]}, queue.top())) {
                    queue.push({nums1[i], nums2[j]});
                    queue.pop();
                }
            }
        }
        while (queue.size()) {
            ans.push_back({queue.top().first, queue.top().second});
            queue.pop();
        }
        return ans;
    }
};

Java

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        PriorityQueue<List<Integer>> queue = new PriorityQueue<>(new Comparator<>(){
            public int compare(List<Integer> a, List<Integer> b) {
                return (b.get(0) + b.get(1)) - (a.get(0) + a.get(1));
            }
        });
        // 也可以这样写
        // PriorityQueue<List<Integer>> queue = new PriorityQueue<>((a, b)->(
        //     (b.get(0) + b.get(1) - a.get(0) - a.get(1))
        // ));
        for (int i = 0; i < nums1.length && i < k; i++) {
            for (int j = 0; j < nums2.length && j < k; j++) {
                queue.offer(new ArrayList(Arrays.asList(nums1[i], nums2[j])));
                if (queue.size() > k) queue.poll();
            }
        }
        while (queue.size() > 0) {
            ans.add(queue.poll());
        }
        return ans;
    }
}

四，解题过程

第一博

借助优先队列——小根堆，双重循环将每一个可能的结果放进去，然后返回队列中的内容。

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        PriorityQueue<List<Integer>> queue = new PriorityQueue<>(new Comparator<>(){
            public int compare(List<Integer> a, List<Integer> b) {
                return (b.get(0) + b.get(1)) - (a.get(0) + a.get(1));
            }
        });
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                queue.offer(new ArrayList(Arrays.asList(nums1[i], nums2[j])));
                if (queue.size() > k) queue.poll();
            }
        }
        while (queue.size() > 0) {
            ans.add(queue.peek());
            queue.poll();
        }
        return ans;
    }
}