每日算法--2023.2.25

1.力扣373--和最小的k个数对

class Solution {
    class Node{
        public int sum;
        public int i;
        public int j;
        Node(int sum, int i, int j){
            this.i = i;this.j = j;
            this.sum = sum;
        }
    }
    //解题思路：一共有m*n个数对，可以排列成m端有序的数对，相当于多路归并排序找topK
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        List<List<Integer>> res = new LinkedList<>();
         PriorityQueue<Node> minHeap = new PriorityQueue<>((o1,o2)->(o1.sum-o2.sum));
         for(int i = 0;i<m;i++){
             minHeap.offer(new Node(nums1[i]+nums2[0],i ,0));
         }
         while(!minHeap.isEmpty()){
             Node cur = minHeap.poll();
             List<Integer> temp = new LinkedList<>();
             temp.add(nums1[cur.i]);temp.add(nums2[cur.j]);
             res.add(temp);
             if(res.size() == k){
                 return res;
             }
             if(cur.j<n-1){
                 minHeap.offer(new Node(nums1[cur.i]+nums2[cur.j+1],cur.i,cur.j+1));
             }
         }
         return res;
    }
}