Medium
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.
Note:
You may assume k is always valid, 1 ≤ k ≤ n2.
先送你一句話(huà)：
why? 因?yàn)橛枚炎鰧?shí)在是太簡(jiǎn)單了缩功，根本不用去考慮二維數(shù)組（ matrix) 里的數(shù)字究竟是s型遞增還是其他，just put them all into a max heap, and poll() untill there's only k elements in the heap. 我們要找的就是剩下的元素里最大的那個(gè), 所以peek()一下就好了逝撬。 注意一下冷溃，默認(rèn)的PriorityQueue是一個(gè)minHeap, 所以要自己改寫(xiě)Comparator.
順便回憶了一下如何寫(xiě)PriorityQueue的Constructor以及自定義Comparator.
PriorityQueue(int initialCapacity, Comparator<? super [E]> comparator)
Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
PriorityQueue<Integer> pq = new PriorityQueue<>(n * n, maxHeap);
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
pq.add(matrix[i][j]);
}
}
while (pq.size() > k){
pq.poll();
}
return pq.peek();
}
private Comparator<Integer> maxHeap = new Comparator<Integer>(){
public int compare(Integer a, Integer b){
return b - a;
}
};
}
這道題是可以繼續(xù)優(yōu)化的钱磅，但我還暫時(shí)看不懂http://www.jiuzhang.com/solutions/kth-smallest-number-in-sorted-matrix/
的解法。
