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
image1
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. 😉😃💗