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.

Solution1：Heap

思路：建立一個n個大小的大頂堆keep n個當(dāng)前最小的數(shù)。初始化為第一行黔寇，poll一個a(最小的)珍德，作為第一小玄呛，push一個a同列下面的入堆繼續(xù)比較护姆，再poll一個最為第二小诉探，直到k個。
入堆的都是最小的candidate洞就，出堆的是全局遞增的盆繁。

屏幕快照 2017-09-07 下午9.11.57.png

Time Complexity: O(n + klogn) Space Complexity: O(n)

Solution2：Binary Search in value domain

思路： 二分值域=mid，數(shù)出<=mid的元素個數(shù)旬蟋，如果<k油昂，則在值域mid以下找，反之在mid以上倾贰，這樣二分冕碟，最后的值域=result
Time Complexity: O(n^2 log(val_diff))
在列尋找的時候再用Binary search 可以變?yōu)镺(nlogn log(val_diff))
Space Complexity: O(1)

Solution1 Code：

class Solution1 {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        PriorityQueue<Tuple> queue = new PriorityQueue<Tuple>();
        // first row
        for(int j = 0; j <= n - 1; j++) queue.offer(new Tuple(0, j, matrix[0][j]));
        
        // get one and push its element below in the same column 
        for(int i = 0; i < k - 1; i++) {
            Tuple t = queue.poll();
            if(t.x == n - 1) continue;
            pq.offer(new Tuple(t.row + 1, t.col, matrix[t.row + 1][t.col]));
        }
        return pq.poll().val;
    }
}

class Tuple implements Comparable<Tuple> {
    int row, col, val;
    public Tuple (int row, int col, int val) {
        this.row = row;
        this.col = col;
        this.val = val;
    }
    
    @Override
    public int compareTo (Tuple that) {
        return this.val - that.val;
    }
}

Solution2 Code：

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int lo = matrix[0][0], hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1;//[lo, hi)
        while(lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0;
            for(int row = 0; row < matrix.length; row++) {
                for(int col = 0; col < matrix[0].length; col++) //could do another binary search here
                    if(matrix[row][col] <= mid) count += 1;
            }
            if(count < k) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}