By Long Luo
This article is the solution 3 Approaches: Sorting, Merge Sort, Binary Search of Problem 378. Kth Smallest Element in a Sorted Matrix.
Here shows 3 Approaches to slove this problem: Sorting, Merge Sort, Binary Search.
Sorting
1 2 3 4 5 6 7 8 9 10 11 12 13
| public int kthSmallest(int[][] matrix, int k) { int n = matrix.length; int[] array = new int[n * n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { array[i * n + j] = matrix[i][j]; } }
Arrays.sort(array);
return array[k - 1]; }
|
Analysis
- Time Complexity: \(O(n^2logn)\)
- Space Complexity: \(O(n^2)\)
Merge Sort
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| public int kthSmallest(int[][] matrix, int k) { int n = matrix.length;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);
for (int i = 0; i < n; i++) { pq.offer(new int[]{matrix[i][0], i, 0}); }
for (int i = 0; i < k - 1; i++) { int[] cur = pq.poll();
if (cur[2] != n - 1) { pq.offer(new int[]{matrix[cur[1]][cur[2] + 1], cur[1], cur[2] + 1}); } }
return pq.poll()[0]; }
|
Analysis
- Time Complexity: \(O(klogn)\)
- Space Complexity: \(O(n)\)
Binary Search
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| public int kthSmallest(int[][] matrix, int k) { int n = matrix.length;
int left = matrix[0][0]; int right = matrix[n - 1][n - 1];
while (left < right) { int mid = left + (right - left) / 2;
if (check(matrix, mid, k, n)) { right = mid; } else { left = mid + 1; } }
return left; }
private static boolean check(int[][] matrix, int target, int k, int n) { int i = n - 1; int j = 0; int num = 0;
while (i >= 0 && j < n) { if (matrix[i][j] <= target) { num += i + 1; j++; } else { i--; } } return num >= k; }
|
Analysis
- Time Complexity: \(O(nlog(r-l)\)
- Space Complexity: \(O(1)\)
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗