# 378 Kth Smallest Element in a Sorted Matrix

給一整數二維矩陣，由左而右、由上而下ascending排序，找出第k小的數字。

Idea

這個解法滿不錯的。

他的邏輯是用value來當作search space，先定出左邊界(lo)跟右邊界(hi)，然後用lo跟hi算出mid，再從頭數多少個數字小於mid，如果count太大表示mid太大，應該把hi縮小；反之應該增加lo。

Pseudocode

int lo = current smallest number, hi = current largest number

while(lo < hi)
    int mid = lo + (hi-lo)/2
    go through each row
        start from last col,
        while matrix[row][col] > mid, col-- until find a number smaller than mid
        count = how many number < mid

        if(count == k) kth smallest found
        else if(count < k) set current smallest num to mid +1
        else    set current largest num to mid

    return lo

Code

public 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,  j = matrix[0].length - 1;
            for(int i = 0; i < matrix.length; i++) {
                while(j >= 0 && matrix[i][j] > mid) j--;
                count += (j + 1);
            }
            if(count < k) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}