leetcode【373】查找和最小的k对数字

Dear 丶 2021-10-03 01:34 271阅读 0赞

给定两个以升序排列的整形数组 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\]  
解释: 返回序列中的前 3 对数：  
     \[1,2\],\[1,4\],\[1,6\],\[7,2\],\[7,4\],\[11,2\],\[7,6\],\[11,4\],\[11,6\]  
示例 2:

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

输入: nums1 = \[1,2\], nums2 = \[3\], k = 3   
输出: \[1,3\],\[2,3\]  
解释: 也可能序列中所有的数对都被返回:\[1,3\],\[2,3\]

解题思路：求解K大K小问题就会用到堆，而优先队列就是堆结构，所以可以使用优先队列找到K项，然后进行暴力，就会缩短时间复杂度。

代码：

public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            LinkedList<List<Integer>> list = new LinkedList();
            PriorityQueue<List<Integer>>queue=new  PriorityQueue<>(k,new  Comparator<List<Integer>>() {
                @Override
                public int compare(List<Integer> o1,  List<Integer> o2) {
                    // TODO Auto-generated method  stub
                    int sum1=0,sum2=0;
                    for(int i=0;i<o1.size();i++) {
                        sum1+=o1.get(i);
                    }
                    for(int i=0;i<o1.size();i++) {
                        sum2+=o2.get(i);
                    }
                    return sum2-sum1;
                }
            });
        for(int i=0;i<nums1.length;i++){
            for(int j = 0;j<nums2.length;j++){
                List<Integer> list1 = new LinkedList<>();
                list1.add(nums1[i]);
                list1.add(nums2[j]);
                queue.add(list1);
                if(queue.size() > k){
                    queue.poll();
                }
            }
        }
        while (! queue.isEmpty()){
            List<Integer> linkedList = new LinkedList<>();
            linkedList = queue.poll();
            list.add(linkedList);
        }
        LinkedList<List<Integer>> list1 = new LinkedList();
        for(int i = list.size()-1;i>=0;i--){
            list1.add(list.get(i));
        }
        return list1;
        }