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

思路：建立一個(gè)n個(gè)大小的大頂堆keep n個(gè)當(dāng)前最小的數(shù)。初始化為第一行，poll一個(gè)a(最小的)，作為第一小，push一個(gè)a同列下面的入堆繼續(xù)比較，再poll一個(gè)最為第二小，直到k個(gè)。
入堆的都是最小的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的元素個(gè)數(shù)，如果<k，則在值域mid以下找，反之在mid以上，這樣二分，最后的值域=result
Time Complexity: O(n^2 log(val_diff))
在列尋找的時(shí)候再用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;
    }
}