|
6 | 6 | importjava.util.Queue; |
7 | 7 |
|
8 | 8 | publicclass_373 { |
9 | | -publicstaticclassSolution1 { |
10 | 9 |
|
11 | | -finalint[][]neighbors =newint[][]{{0,1}, {1,0}}; |
12 | | - |
13 | | -publicList<int[]>kSmallestPairs(int[]nums1,int[]nums2,intk) { |
14 | | -List<int[]>result =newArrayList<>(); |
15 | | -if (nums1 ==null |
16 | | - ||nums2 ==null |
17 | | - ||k ==0 |
18 | | - ||nums1.length ==0 |
19 | | - ||nums2.length ==0) { |
20 | | -returnresult; |
21 | | - } |
22 | | -Queue<Pair>meanHeap =newPriorityQueue<>(); |
23 | | -meanHeap.offer(newPair(0,0,nums1[0] +nums2[0])); |
24 | | -boolean[][]visited =newboolean[nums1.length][nums2.length]; |
25 | | -visited[0][0] =true;//we start form (0,0), so mark it as visited |
26 | | -while (k >0 && !meanHeap.isEmpty()) { |
27 | | -Pairpair =meanHeap.poll(); |
28 | | -result.add(newint[]{nums1[pair.row],nums2[pair.col]}); |
29 | | -k--; |
30 | | -for (int[]neighbor :neighbors) { |
31 | | -intnextRow =pair.row +neighbor[0]; |
32 | | -intnextCol =pair.col +neighbor[1]; |
33 | | -if (nextRow <0 |
34 | | - ||nextCol <0 |
35 | | - ||nextRow >=nums1.length |
36 | | - ||nextCol >=nums2.length |
37 | | - ||visited[nextRow][nextCol]) { |
38 | | -continue; |
39 | | - } |
40 | | -visited[nextRow][nextCol] =true; |
41 | | -meanHeap.offer(newPair(nextRow,nextCol,nums1[nextRow] +nums2[nextCol])); |
42 | | - } |
43 | | - } |
44 | | - |
45 | | -returnresult; |
46 | | - } |
47 | | - |
48 | | -classPairimplementsComparable<Pair> { |
49 | | -introw; |
50 | | -intcol; |
51 | | -intsum; |
52 | | - |
53 | | -publicPair(introw,intcol,intsum) { |
54 | | -this.row =row; |
55 | | -this.col =col; |
56 | | -this.sum =sum; |
57 | | - } |
58 | | - |
59 | | -@Override |
60 | | -publicintcompareTo(Pairthat) { |
61 | | -returnthis.sum -that.sum; |
| 10 | +publicclassSolution { |
| 11 | + |
| 12 | +int[][]dirs = {{0,1},{1,0},{1,1}}; |
| 13 | +publicList<List<Integer>>kSmallestPairs(int[]nums1,int[]nums2,intk) { |
| 14 | + |
| 15 | +List<List<Integer>>result =newArrayList<>(); |
| 16 | + |
| 17 | +// EDGE CASE |
| 18 | +if(nums1==null ||nums2==null ||nums1.length==0 ||nums2.length==0)returnresult; |
| 19 | + |
| 20 | +// visited array |
| 21 | +boolean[][]visited =newboolean[nums1.length][nums2.length]; |
| 22 | + |
| 23 | +// Min Heap |
| 24 | +PriorityQueue<int[]>pq =newPriorityQueue<>((a,b)->{ |
| 25 | +return (a[0]+a[1] ) - (b[0]+b[1] ) ; |
| 26 | + }); |
| 27 | + |
| 28 | +int[]temp =newint[]{nums1[0],nums2[0],0,0}; |
| 29 | +pq.add(temp); |
| 30 | +visited[0][0]=true; |
| 31 | + |
| 32 | +while(!pq.isEmpty()){ |
| 33 | +int[]arr =pq.poll(); |
| 34 | +List<Integer>ls =newArrayList<>(); |
| 35 | +ls.add(arr[0]);ls.add(arr[1]); |
| 36 | +result.add(ls); |
| 37 | + |
| 38 | +if(result.size()==k)break; |
| 39 | +inti=arr[2],j=arr[3]; |
| 40 | + |
| 41 | +for(int[]dir :dirs){ |
| 42 | +intdx=i+dir[0],dy=j+dir[1]; |
| 43 | +if(dx<0 ||dx>=nums1.length ||dy<0 ||dy>=nums2.length ||visited[dx][dy])continue; |
| 44 | +pq.add(newint[]{nums1[dx],nums2[dy],dx,dy}); |
| 45 | +visited[dx][dy] =true; |
62 | 46 | } |
63 | 47 | } |
| 48 | +returnresult; |
64 | 49 | } |
| 50 | + } |
65 | 51 | } |