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; } }
标签:25,cur,temp,--,res,sum,2023.2,int,public From: https://www.cnblogs.com/lyjps/p/17154078.html