|
1 | | -classSolution { |
2 | | -publicList<int[]>kSmallestPairs(int[]nums1,int[]nums2,intk) { |
3 | | -List<int[]>ans =newArrayList<>(); |
4 | | - |
5 | | -if (nums1.length ==0 ||nums2.length ==0 ||k ==0) { |
6 | | -returnans; |
7 | | - } |
8 | | - |
9 | | -PriorityQueue<Element>pq =newPriorityQueue<>(newComparator<Element>() { |
10 | | -@Override |
11 | | -publicintcompare(Elemento1,Elemento2) { |
12 | | -return (o1.x +o1.y) - (o2.x +o2.y); |
13 | | - } |
14 | | - }); |
15 | | - |
16 | | -for (inti=0;i<nums2.length &&i <k;i++) { |
17 | | -pq.offer(newElement(0,nums2[i],nums1[0])); |
18 | | - } |
19 | | - |
| 1 | +classSolution { |
| 2 | +publicList<List<Integer>>kSmallestPairs(int[]nums1,int[]nums2,intk) { |
| 3 | +PriorityQueue<int[]>pq =newPriorityQueue<>((a,b) ->a[2] -b[2]); |
| 4 | +List<List<Integer>>result =newArrayList<>(); |
| 5 | +Set<Pair<Integer,Integer>>visited =newHashSet<>(); |
| 6 | +pq.add(newint[]{0,0,nums1[0] +nums2[0]}); |
| 7 | +visited.add(newPair<Integer,Integer>(0,0)); |
20 | 8 | while (k-- >0 && !pq.isEmpty()) { |
21 | | -Elementtemp =pq.poll(); |
22 | | -ans.add(newint[]{temp.y,temp.x}); |
23 | | - |
24 | | -if (temp.idx >=nums1.length-1) { |
25 | | -continue; |
| 9 | +int[]removed =pq.poll(); |
| 10 | +inti =removed[0]; |
| 11 | +intj =removed[1]; |
| 12 | +result.add(List.of(nums1[i],nums2[j])); |
| 13 | +Pair<Integer,Integer>nums1Pair =newPair<Integer,Integer>(i +1,j); |
| 14 | +Pair<Integer,Integer>nums2Pair =newPair<Integer,Integer>(i,j +1); |
| 15 | +if (i +1 <nums1.length && !visited.contains(nums1Pair)) { |
| 16 | +pq.add(newint[]{i +1,j,nums1[i +1] +nums2[j]}); |
| 17 | +visited.add(nums1Pair); |
| 18 | + } |
| 19 | +if (j +1 <nums2.length && !visited.contains(nums2Pair)) { |
| 20 | +pq.add(newint[]{i,j +1,nums1[i] +nums2[j +1]}); |
| 21 | +visited.add(nums2Pair); |
26 | 22 | } |
27 | | - |
28 | | -pq.offer(newElement(temp.idx+1,temp.x,nums1[temp.idx+1])); |
29 | | - } |
30 | | - |
31 | | -returnans; |
32 | | - } |
33 | | - |
34 | | -classElement { |
35 | | -intidx; |
36 | | -intx; |
37 | | -inty; |
38 | | - |
39 | | -publicElement(intval,intx,inty) { |
40 | | -this.idx =val; |
41 | | -this.x =x; |
42 | | -this.y =y; |
43 | | - } |
44 | | - |
45 | | -@Override |
46 | | -publicStringtoString() { |
47 | | -return"Element{" + |
48 | | -"idx=" +idx + |
49 | | -", x=" +x + |
50 | | -", y=" +y + |
51 | | -'}'; |
52 | 23 | } |
| 24 | +returnresult; |
53 | 25 | } |
54 | 26 | } |