2022-8-23 剑指offer-优先队列（堆）-每日一题-太难不写了

剑指 Offer II 061. 和最小的 k 个数对

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

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

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

 1 class Solution {
 2     public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
 3         PriorityQueue<int[]> q=new PriorityQueue<>((a,b)->(a[0]+a[1]-b[0]-b[1]));
 4         for (int i=0;i<nums1.length;i++){
 5             for (int j=0;j<nums2.length;j++){
 6                 int[] temp=new int[]{nums1[i],nums2[j]};
 7                 q.offer(temp);
 8             }
 9         }
10         List<List<Integer>> ans=new ArrayList<>();
11         for (int i=0;i<k;i++){
12             List<Integer> list=new ArrayList<>();
13             if (q.size()==0) break;
14             int[] arr=q.poll();
15             list.add(arr[0]);
16             list.add(arr[1]);
17             ans.add(list);
18         }
19         return ans;
20     }
21 }

思路：优先队列。但是可以根据有序巧妙的记录所有（0，0），（1，0），。。每次取出将第二个下标+1。