|
1 | 1 | packageg0301_0400.s0373_find_k_pairs_with_smallest_sums; |
2 | 2 |
|
3 | 3 | // #Medium #Array #Heap_Priority_Queue #Top_Interview_150_Heap |
4 | | -// #2025_03_09_Time_0_ms_(100.00%)_Space_57.66_MB_(90.88%) |
| 4 | +// #2025_03_09_Time_27_ms_(90.23%)_Space_58.22_MB_(77.32%) |
5 | 5 |
|
6 | | -importjava.util.AbstractList; |
7 | 6 | importjava.util.ArrayList; |
8 | | -importjava.util.Arrays; |
9 | 7 | importjava.util.List; |
| 8 | +importjava.util.PriorityQueue; |
10 | 9 |
|
11 | 10 | publicclassSolution { |
12 | | -publicList<List<Integer>>kSmallestPairs(int[]nums1,int[]nums2,intk) { |
13 | | -returnnewAbstractList<List<Integer>>() { |
14 | | -privateList<List<Integer>>pairs; |
15 | | - |
16 | | -@Override |
17 | | -publicList<Integer>get(intindex) { |
18 | | -init(); |
19 | | -returnpairs.get(index); |
20 | | - } |
21 | | - |
22 | | -@Override |
23 | | -publicintsize() { |
24 | | -init(); |
25 | | -returnpairs.size(); |
26 | | - } |
27 | | - |
28 | | -privatevoidload() { |
29 | | -intn =nums1.length; |
30 | | -intm =nums2.length; |
31 | | -intleft =nums1[0] +nums2[0]; |
32 | | -intright =nums1[n -1] +nums2[m -1]; |
33 | | -intmiddle; |
34 | | - |
35 | | -while (left <=right) { |
36 | | -middle = (left +right) /2; |
37 | | -longcount =getCount(nums1,nums2,middle,k); |
38 | | -if (count <k) { |
39 | | -left =middle +1; |
40 | | - }elseif (count >k) { |
41 | | -right =middle -1; |
42 | | - }else { |
43 | | -left =middle; |
44 | | -break; |
45 | | - } |
46 | | - } |
47 | | -getPairs(nums1,nums2,left,k); |
48 | | - } |
49 | | - |
50 | | -privatelonggetCount(int[]nums1,int[]nums2,intgoal,intk) { |
51 | | -intprevRight =nums2.length -1; |
52 | | -intcount =0; |
53 | | - |
54 | | -for (inti =0;i <nums1.length &&nums1[i] +nums2[0] <=goal;i++) { |
55 | | -intleft =0; |
56 | | -intright =prevRight; |
57 | | -intposition = -1; |
58 | | -while (left <=right) { |
59 | | -intmiddle = (right +left) /2; |
60 | | -intsum =nums1[i] +nums2[middle]; |
61 | | -if (sum <=goal) { |
62 | | -position =middle; |
63 | | -left =middle +1; |
64 | | - }else { |
65 | | -right =middle -1; |
66 | | - } |
67 | | - } |
68 | | -if (position >=0) { |
69 | | -count +=position +1; |
70 | | -prevRight =position; |
71 | | - } |
72 | | -if (count >k) { |
73 | | -returncount; |
74 | | - } |
75 | | - } |
76 | | -returncount; |
77 | | - } |
78 | | - |
79 | | -privatevoidgetPairs(int[]nums1,int[]nums2,intsum,intk) { |
80 | | -pairs =newArrayList<>(); |
81 | | -for (intitem :nums1) { |
82 | | -for (intj =0;j <nums2.length &&item +nums2[j] <sum;j++) { |
83 | | -pairs.add(Arrays.asList(item,nums2[j])); |
84 | | - } |
85 | | - } |
86 | | -for (intvalue :nums1) { |
87 | | -for (intj =0; |
88 | | -j <nums2.length &&value +nums2[j] <=sum &&pairs.size() <k; |
89 | | -j++) { |
90 | | -if (value +nums2[j] ==sum) { |
91 | | -pairs.add(Arrays.asList(value,nums2[j])); |
92 | | - } |
93 | | - } |
94 | | - } |
95 | | - } |
| 11 | +privatestaticclassNode { |
| 12 | +longsum; |
| 13 | +List<Integer>al; |
| 14 | +intindex; |
| 15 | + |
| 16 | +Node(intindex,intnum1,intnum2) { |
| 17 | +this.sum = (long)num1 + (long)num2; |
| 18 | +this.al =newArrayList<>(); |
| 19 | +this.al.add(num1); |
| 20 | +this.al.add(num2); |
| 21 | +this.index =index; |
| 22 | + } |
| 23 | + } |
96 | 24 |
|
97 | | -publicvoidinit() { |
98 | | -if (null ==pairs) { |
99 | | -load(); |
100 | | - } |
| 25 | +publicList<List<Integer>>kSmallestPairs(int[]nums1,int[]nums2,intk) { |
| 26 | +PriorityQueue<Node>queue =newPriorityQueue<>((a,b) ->a.sum <b.sum ? -1 :1); |
| 27 | +List<List<Integer>>res =newArrayList<>(); |
| 28 | +for (inti =0;i <nums1.length &&i <k;i++) { |
| 29 | +queue.add(newNode(0,nums1[i],nums2[0])); |
| 30 | + } |
| 31 | +for (inti =1;i <=k && !queue.isEmpty();i++) { |
| 32 | +Nodecur =queue.poll(); |
| 33 | +res.add(cur.al); |
| 34 | +intnext =cur.index; |
| 35 | +intlastNum1 =cur.al.get(0); |
| 36 | +if (next +1 <nums2.length) { |
| 37 | +queue.add(newNode(next +1,lastNum1,nums2[next +1])); |
101 | 38 | } |
102 | | - }; |
| 39 | + } |
| 40 | +returnres; |
103 | 41 | } |
104 | 42 | } |