The only clear explanation I can find from the web
四刷 08/2022
Version #1 Min Heap
Time O(KlogK) 这里只有logK因为每次只加1to2 new nodes
Space O(K)
Runtime: 24 ms, faster than 47.59% of Java online submissions for Kth Smallest Element in a Sorted Matrix.
Memory Usage: 46.6 MB, less than 99.18% of Java online submissions for Kth Smallest Element in a Sorted Matrix.
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int rows = matrix.length;
int cols = matrix[0].length;
Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(matrix[a[0]][a[1]], matrix[b[0]][b[1]]));
minHeap.offer(new int[]{0, 0});
int[] curr = new int[2];
while (k-- > 0) {
curr = minHeap.poll();
if (curr[0] == 0 && curr[1] < cols - 1) {
minHeap.offer(new int[]{curr[0], curr[1] + 1});
}
if (curr[0] + 1 < rows) {
minHeap.offer(new int[]{curr[0] + 1, curr[1]});
}
}
return matrix[curr[0]][curr[1]];
}
}
三刷 06/2022
Version #1 Min Heap
注意这里不是无脑加每个点的(x+1, y) 和(x, y+1)因为会有重复
应该是只有遇到第一个row的之后才向右展开
Time O(KlogK)
Space O(K)
Runtime: 31 ms, faster than 25.29% of Java online submissions for Kth Smallest Element in a Sorted Matrix.
Memory Usage: 57.1 MB, less than 34.39% of Java online submissions for Kth Smallest Element in a Sorted Matrix.
class Solution {
public int kthSmallest(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
throw new IllegalArgumentException("the matrix cannot be empty");
}
int rows = matrix.length;
int cols = matrix[0].length;
// int[] - x, y
Queue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(matrix[a[1]][a[0]], matrix[b[1]][b[0]]));
minHeap.offer(new int[]{0, 0});
int cnt = 0;
while (!minHeap.isEmpty()) {
cnt++;
int[] curr = minHeap.poll();
int y = curr[1];
int x = curr[0];
if (cnt == k) {
return matrix[y][x];
}
if (y + 1 < rows) {
minHeap.offer(new int[]{x, y + 1});
}
// Only expand to the right when it's the first row
if (y == 0 && x + 1 < cols) {
minHeap.offer(new int[]{x + 1, y});
}
}
throw new RuntimeException("the total elements in the matric is less than k");
}
}
Version #2 Binary Search
有一个很关键的点是如何保证binary seach出来的数字一定在matrix里面
Since we are looking for the smallest number from min to max that has k numbers less than or equals to itself
For example 1, 3, 5, 7 -- k = 2
Then any number int [3, 5) will satisfy the criteria, but the smallest number must be 3, which is in the matrix
第二个关键的问题是count smaller or equals to 的时候，是从左下角x = 0, y = rows - 1开始的
Time O(Nlog(max - min))
Space O(1)
class Solution {
public int kthSmallest(int[][] matrix, int k) {
// Find the first number that k elements less than or equals to itself
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
throw new IllegalArgumentException("the matrix cannot be empty");
}
int start = matrix[0][0], end = matrix[matrix.length - 1][matrix[0].length - 1];
while (start < end) {
int mid = start + (end - start) / 2;
int count = countSmallerOrEqual(matrix, mid);
if (count < k) {
start = mid + 1;
} else { // count >= k, end = mid
end = mid;
}
}
return start;
}
private int countSmallerOrEqual(int[][] matrix, int num) {
int y = matrix.length - 1;
int x = 0;
int cnt = 0;
while (x < matrix[0].length && y >= 0) {
if (matrix[y][x] > num) {
y--;
} else {
cnt += y + 1;
x++;
}
}
return cnt;
}
}
一刷
Version #1min heap with extra visited array
Time: O(klogk)
Space: O(k) for heap O(mn) for the visited array
12.87%
class Cell {
public int x, y;
public int val;
public Cell(int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}
}
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) throw new IllegalArgumentException();
int count = 0;
int rows = matrix.length;
int cols = matrix[0].length;
Set<Integer> visited = new HashSet<>();
PriorityQueue<Cell> que = new PriorityQueue<>(k, new Comparator<Cell>() {
public int compare(Cell c1, Cell c2) {
if (c1.val == c2.val) return 0;
return c1.val < c2.val ? -1 : 1;
}
});
que.add(new Cell(0, 0, matrix[0][0]));
visited.add(0 * cols + 0);
while (!que.isEmpty()) {
Cell curr = que.poll();
count++;
if (count == k) return curr.val;
int x = curr.x;
int y = curr.y;
if (x + 1 < rows && !visited.contains((x + 1) * cols + y)) {
que.add(new Cell(x + 1, y, matrix[x + 1][y]));
visited.add((x + 1) * cols + y);
}
if (y + 1 < cols && !visited.contains(x * cols + y + 1)) {
que.add(new Cell(x, y + 1, matrix[x][y + 1]));
visited.add(x * cols + y + 1);
}
}
return -1;
}
}
Version #2 min heap without visited array (polished)
一刷TODO 二刷写的这个Version
感觉已经很漂亮了
二分法的方法做的不是特别透彻
39.97 %
class Cell {
public int x, y;
public int val;
public Cell(int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}
}
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0 || k <= 0) throw new IllegalArgumentException();
int rows = matrix.length;
int cols = matrix[0].length;
Queue<Cell> minHeap = new PriorityQueue<>(k, new Comparator<Cell>(){
@Override
public int compare(Cell c1, Cell c2) {
return c1.val - c2.val;
}
});
minHeap.offer(new Cell(0, 0, matrix[0][0]));
Cell curr;
for (int i = 1; i < k; i++) {
curr = minHeap.poll();
if (curr.x == 0 && curr.y + 1 < cols) {
minHeap.offer(new Cell(curr.x, curr.y + 1, matrix[curr.x][curr.y + 1]));
}
if (curr.x + 1 < rows) minHeap.offer(new Cell(curr.x + 1, curr.y, matrix[curr.x + 1][curr.y]));
}
return minHeap.peek().val;
}
}
Version #3 Binary Search
Time: O()
73.44%
public class Solution {
public int kthSmallest(int[][] matrix, int k) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) throw new IllegalArgumentException();
int low = matrix[0][0], high = matrix[matrix.length - 1][matrix[0].length - 1];
int mid, count;
while (low < high) {
mid = low + (high - low) / 2;
count = search(matrix, mid);
//TODO
if (count < k) {
low = mid + 1;
} else {
high = mid;
}
//System.out.println("count" + count + "low:" + low + " high:" + high);
}
return low;
}
//numbers smaller or equal to target
private int search(int[][] matrix, int target) {
int i = matrix.length - 1, j = 0;
int count = 0;
while (i >= 0 && j < matrix[0].length) {
if (matrix[i][j] <= target) {
count = count + i + 1;
j++;
} else {
i--;
}
}
return count;
}
}
No comments:
Post a Comment