Leetcode刷题100天—373. 查找和最小的K对数字(优先队列)—day17

小咪咪 2022-08-28 15:55 117阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210824223828887][]

给定两个以升序排列的整数数组 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]

提示:

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

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

致命问题：如何将最符合要求的数放入到队列中

package 优先队列;
    
    import java.util.Comparator;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.PriorityQueue;
    /* * 6 * https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/ */
    //此题使用优先队列（小顶堆），通过双重for循环遍历
    public class _373_查找和最小的K对数字 { 
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) { 
        	List<List<Integer>> res=new LinkedList<List<Integer>>();
    // 设置优先队列
        	PriorityQueue<Data> queue=new PriorityQueue<>(new Comparator<Data>() { 
        		
        		public int compare(Data o1,Data o2) { 
    				return o1.get()-o2.get();//小顶堆
    			}
    		});
    // 第一层循环遍历num1
        	for(int i=0;i<(nums1.length<k?nums1.length:k);i++) { 
    // 第二层遍历nums2
        		for(int j=0;j<(nums2.length<k?nums2.length:k);j++) { 
    // 组合存入到优先队列中
                    // if(nums2[j]){ 
    
                    // }
        			queue.offer(new Data(nums1[i],nums2[j]));
        		}
        	}
    // 通过for循环遍历前k个数据
            int num=k>queue.size()?queue.size():k;
            // System.out.print(num);
        	for(int i=0;i<num;i++) { 
                // 
        		Data j=(Data)queue.poll();
        		List<Integer> re=new LinkedList<>();
        		re.add(j.num1);
        		re.add(j.num2);
       		    // System.out.print(j.num1+" "+j.num2);
        		res.add(re);
                // re.clear();
        		
        	}
        	return res;
        }
    // 设置数据类
        public class Data{ 
        	int  num1;
        	int num2;
        	public  Data(int num1,int num2) { 
    			this.num1=num1;
    			this.num2=num2;
                
    		}
            public int get(){ 
                return this.num1+this.num2;
            }
        	public  int get1() { 
    			return this.num1;
    		}
        	public  int get2() { 
    			return this.num2;
    		}
        }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210824223828887]: /images/20220828/8e71fe18ae674b0da978c1cfd3e5ff24.png