http://www.lintcode.com/en/problem/kth-smallest-number-in-sorted-matrix/
Basically, you put the elements of the first column into a heap and track the row they came from. At each step, you remove the minimum element from the heap and push the next element from the row it came from (if you reach the end of the row, then you don't push anything). Both removing the minimum and adding a new element cost O(log n). At the jth step, you remove the
For the matrix above, you initially start with
http://www.cnblogs.com/EdwardLiu/p/5137039.html
实际上是和丑数问题类似的一个问题，也是使用一个优先队列
From http://www.geeksforgeeks.org/kth-smallest-element-in-a-row-wise-and-column-wise-sorted-2d-array-set-1/
2) Do following k times.
…a) Get minimum element (or root) from min heap.
…b) Find row number and column number of the minimum element.
…c) Replace root with the next element from same column and min-heapify the root.
3) Return the last extracted root.
https://codesolutiony.wordpress.com/2015/05/31/lintcode-kth-smallest-number-in-sorted-matrix/
https://github.com/kamyu104/LintCode/blob/master/C++/kth-smallest-number-in-sorted-matrix.cpp
TODO:
https://learn.hackerearth.com/forum/161/kth-largest-element-in-a-2d-array-sorted-along-both-rows-and-columns/
Read full article from arrays - Kth smallest element in sorted matrix - Stack Overflow
Find the kth smallest number in at row and column sorted matrix.
Example
Given k =
4 and a matrix:[
[1 ,5 ,7],
[3 ,7 ,8],
[4 ,8 ,9],
]
return
5
Challenge
O(k log n), n is the maximal number in width and height.
1 3 5
2 4 6
7 8 9Basically, you put the elements of the first column into a heap and track the row they came from. At each step, you remove the minimum element from the heap and push the next element from the row it came from (if you reach the end of the row, then you don't push anything). Both removing the minimum and adding a new element cost O(log n). At the jth step, you remove the
jth smallest element, so after k steps you are done for a total cost of O(k log n) operations (where n is the number of rows in the matrix).For the matrix above, you initially start with
1,2,7 in the heap. You remove 1 and add 3 (since the first row is 1 3 5) to get 2,3,7. You remove 2 and add 4 to get 3,4,7. Remove 3 and add 5 to get 4,5,7. Remove 4 and add 6 to get 5,6,7. Note that we are removing the elements in the globally sorted order. You can see that continuing this process will yield the kth smallest element after k iterations.http://www.cnblogs.com/EdwardLiu/p/5137039.html
9 public class Point { 10 public int x, y, val; 11 public Point(int x, int y, int val) { 12 this.x = x; 13 this.y = y; 14 this.val = val; 15 } 16 } 17 18 Comparator<Point> comp = new Comparator<Point>() { 19 public int compare(Point left, Point right) { 20 return left.val - right.val; 21 } 22 }; 23 24 public int kthSmallest(int[][] matrix, int k) { 25 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { 26 return 0; 27 } 28 if (k > matrix.length * matrix[0].length) { 29 return 0; 30 } 31 return horizontal(matrix, k); 32 } 33 34 private int horizontal(int[][] matrix, int k) { 35 Queue<Point> heap = new PriorityQueue<Point>(k, comp); 36 for (int i = 0; i < Math.min(matrix.length, k); i++) { 37 heap.offer(new Point(i, 0, matrix[i][0])); 38 } 39 for (int i = 0; i < k - 1; i++) { 40 Point curr = heap.poll(); 41 if (curr.y + 1 < matrix[0].length) { 42 heap.offer(new Point(curr.x, curr.y + 1, matrix[curr.x][curr.y + 1])); 43 } 44 } 45 return heap.peek().val; 46 }http://www.cnblogs.com/deepblueme/p/4780676.html
实际上是和丑数问题类似的一个问题，也是使用一个优先队列
From http://www.geeksforgeeks.org/kth-smallest-element-in-a-row-wise-and-column-wise-sorted-2d-array-set-1/
1) Build a min heap which takes O(n) time
2) Heapify k times which takes O(kLogn) time.
Therefore, overall time complexity is O(n + kLogn) time.
1) Build a min heap of elements from first row. A heap entry also stores row number and column number.2) Heapify k times which takes O(kLogn) time.
Therefore, overall time complexity is O(n + kLogn) time.
2) Do following k times.
…a) Get minimum element (or root) from min heap.
…b) Find row number and column number of the minimum element.
…c) Replace root with the next element from same column and min-heapify the root.
3) Return the last extracted root.
https://codesolutiony.wordpress.com/2015/05/31/lintcode-kth-smallest-number-in-sorted-matrix/
public int kthSmallest(final int[][] matrix, int k) { boolean[][] visited = new boolean[matrix.length][matrix[0].length]; PriorityQueue<int[]> heap = new PriorityQueue<int[]>(k, new Comparator<int[]>(){ public int compare(int[] a, int[] b) { return Integer.compare(matrix[a[0]][a[1]], matrix[b[0]][b[1]]); } }); heap.add(new int[]{0,0}); visited[0][0] = true; while (k > 1) { int[] res = heap.remove(); int x = res[0]; int y = res[1]; if (x+1 < matrix.length && visited[x+1][y] == false) { visited[x+1][y] = true; heap.add(new int[]{x+1, y}); } if (y+1 < matrix[0].length && visited[x][y+1] == false) { visited[x][y+1] = true; heap.add(new int[]{x, y+1}); } k--; } int[] res = heap.remove(); return matrix[res[0]][res[1]]; }int kthSmallest(int mat[4][4], int n, int k){ // k must be greater than 0 and smaller than n*n if (k <= 0 || k > n*n) return INT_MAX; // Create a min heap of elements from first row of 2D array HeapNode harr[n]; for (int i = 0; i < n; i++) harr[i] = {mat[0][i], 0, i}; buildHeap(harr, n); HeapNode hr; for (int i = 0; i < k; i++) { // Get current heap root hr = harr[0]; // Get next value from column of root's value. If the // value stored at root was last value in its column, // then assign INFINITE as next value int nextval = (hr.r < (n-1))? mat[hr.r + 1][hr.c]: INT_MAX; // Update heap root with next value harr[0] = {nextval, (hr.r) + 1, hr.c}; // Heapify root minHeapify(harr, 0, n); } // Return the value at last extracted root return hr.val;}private static class Cell implements Comparable<Cell> {
private final int x;
private final int y;
private final int value;
public Cell(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
public int compareTo(Cell that) {
return this.value - that.value;
}
}
private static int findMin(int[][] matrix, int k) {
int min = matrix[0][0];
PriorityQueue<Cell> frontier = new PriorityQueue<>();
frontier.add(new Cell(0, 0, min));
while (k > 1) {
Cell poll = frontier.remove();
if (poll.y + 1 < matrix[poll.x].length) frontier.add(new Cell(poll.x, poll.y + 1, matrix[poll.x][poll.y + 1]));
if (poll.x + 1 < matrix.length) frontier.add(new Cell(poll.x + 1, poll.y, matrix[poll.x + 1][poll.y]));
if (poll.value > min) {
min = poll.value;
k--;
}
}
return min;
}https://github.com/kamyu104/LintCode/blob/master/C++/kth-smallest-number-in-sorted-matrix.cpp
TODO:
https://learn.hackerearth.com/forum/161/kth-largest-element-in-a-2d-array-sorted-along-both-rows-and-columns/
Read full article from arrays - Kth smallest element in sorted matrix - Stack Overflow
