|
7 | 7 |
|
8 | 8 | publicclass_373 { |
9 | 9 |
|
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; |
| 10 | +publicstaticclassSolution1 { |
| 11 | + |
| 12 | +int[][]dirs = {{0,1}, {1,0}, {1,1}}; |
| 13 | + |
| 14 | +publicList<List<Integer>>kSmallestPairs(int[]nums1,int[]nums2,intk) { |
| 15 | + |
| 16 | +List<List<Integer>>result =newArrayList<>(); |
| 17 | + |
| 18 | +// EDGE CASE |
| 19 | +if (nums1 ==null ||nums2 ==null ||nums1.length ==0 ||nums2.length ==0) { |
| 20 | +returnresult; |
| 21 | + } |
| 22 | + |
| 23 | +// visited array |
| 24 | +boolean[][]visited =newboolean[nums1.length][nums2.length]; |
| 25 | + |
| 26 | +// Min Heap |
| 27 | +PriorityQueue<int[]>pq =newPriorityQueue<>((a,b) -> { |
| 28 | +return (a[0] +a[1]) - (b[0] +b[1]); |
| 29 | + }); |
| 30 | + |
| 31 | +int[]temp =newint[]{nums1[0],nums2[0],0,0}; |
| 32 | +pq.add(temp); |
| 33 | +visited[0][0] =true; |
| 34 | + |
| 35 | +while (!pq.isEmpty()) { |
| 36 | +int[]arr =pq.poll(); |
| 37 | +List<Integer>ls =newArrayList<>(); |
| 38 | +ls.add(arr[0]); |
| 39 | +ls.add(arr[1]); |
| 40 | +result.add(ls); |
| 41 | + |
| 42 | +if (result.size() ==k) { |
| 43 | +break; |
| 44 | + } |
| 45 | +inti =arr[2],j =arr[3]; |
| 46 | + |
| 47 | +for (int[]dir :dirs) { |
| 48 | +intdx =i +dir[0]; |
| 49 | +intdy =j +dir[1]; |
| 50 | +if (dx >=0 &&dx <nums1.length &&dy >=0 &&dy <nums2.length && !visited[dx][dy]) { |
| 51 | +pq.add(newint[]{nums1[dx],nums2[dy],dx,dy}); |
| 52 | +visited[dx][dy] =true; |
| 53 | + } |
| 54 | + } |
46 | 55 | } |
| 56 | +returnresult; |
47 | 57 | } |
48 | | -returnresult; |
49 | 58 | } |
50 | | - } |
51 | 59 | } |