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个当前最小的数。初始化为第一行，poll一个a(最小的)，作为第一小，push一个a同列下面的入堆继续比较，再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，数出<=mid的元素个数，如果<k，则在值域mid以下找，反之在mid以上，这样二分，最后的值域=result
Time Complexity: O(n^2 log(val_diff))
在列寻找的时候再用Binary search 可以变为O(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;
    }
}