55import java .util .PriorityQueue ;
66import java .util .Queue ;
77
8- /**
9- * 373. Find K Pairs with Smallest Sums
10- *
11- * You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.
12- * Define a pair (u,v) which consists of one element from the first array and one element from the second array.
13- * Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.
14-
15- Example 1:
16- Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3
17- Return: [1,2],[1,4],[1,6]
18- The first 3 pairs are returned from the sequence:
19- [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
20-
21- Example 2:
22- Given nums1 = [1,1,2], nums2 = [1,2,3], k = 2
23- Return: [1,1],[1,1]
24- The first 2 pairs are returned from the sequence:
25- [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
26-
27- Example 3:
28- Given nums1 = [1,2], nums2 = [3], k = 3
29- Return: [1,3],[2,3]
30- All possible pairs are returned from the sequence:
31- [1,3],[2,3]
32-
33- */
348public class _373 {
359public static class Solution1 {
3610
37- final int [][]neighbors =new int [][]0 ,1 }, {1 ,0 }};
11+ final int [][]neighbors =new int [][]{{0 ,1 }, {1 ,0 }};
3812
3913public List <int []>kSmallestPairs (int []nums1 ,int []nums2 ,int k ) {
4014List <int []>result =new ArrayList <>();
4115if (nums1 ==null
42- ||nums2 ==null
43- ||k ==0
44- ||nums1 .length ==0
45- ||nums2 .length ==0 ) {
16+ nums2 ==null
17+ k ==0
18+ nums1 .length ==0
19+ nums2 .length ==0 ) {
4620return result ;
4721 }
4822Queue <Pair >meanHeap =new PriorityQueue <>();
@@ -51,16 +25,16 @@ public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
5125visited [0 ][0 ] =true ;//we start form (0,0), so mark it as visited
5226while (k >0 && !meanHeap .isEmpty ()) {
5327Pair pair =meanHeap .poll ();
54- result .add (new int []nums1 [pair .row ],nums2 [pair .col ]});
28+ result .add (new int []{nums1 [pair .row ],nums2 [pair .col ]});
5529k --;
5630for (int []neighbor :neighbors ) {
5731int nextRow =pair .row +neighbor [0 ];
5832int nextCol =pair .col +neighbor [1 ];
5933if (nextRow <0
60- ||nextCol <0
61- ||nextRow >=nums1 .length
62- ||nextCol >=nums2 .length
63- ||visited [nextRow ][nextCol ]) {
34+ nextCol <0
35+ nextRow >=nums1 .length
36+ nextCol >=nums2 .length
37+ visited [nextRow ][nextCol ]) {
6438continue ;
6539 }
6640visited [nextRow ][nextCol ] =true ;