給定一個 n x n 矩陣东跪，其中每行和每列元素均按升序排序畸陡，找到矩陣中第k小的元素。
請注意虽填，它是排序后的第k小元素丁恭，而不是第k個元素。
思路非常簡單：
1.找出二維矩陣中最小的數(shù)left斋日，最大的數(shù)right牲览，那么第k小的數(shù)必定在left~right之間
2.mid=(left+right) / 2；在二維矩陣中尋找小于等于mid的元素個數(shù)count
3.若這個count小于k恶守，表明第k小的數(shù)在右半部分且不包含mid第献，即left=mid+1, right=right，又保證了第k小的數(shù)在left~right之間
4.若這個count大于k兔港，表明第k小的數(shù)在左半部分且可能包含mid庸毫，即left=left, right=mid，又保證了第k小的數(shù)在left~right之間
5.因為每次循環(huán)中都保證了第k小的數(shù)在left~right之間衫樊，當(dāng)left==right時飒赃，第k小的數(shù)即被找出利花，等于right
public int kthSmallest(int[][] matrix, int k) {
int row = matrix.length;
int col = matrix[0].length;
int left = matrix[0][0];
int right = matrix[row - 1][col - 1];
while (left < right) {
// 每次循環(huán)都保證第K小的數(shù)在start~end之間，當(dāng)start==end载佳，第k小的數(shù)就是start
int mid = (left + right) / 2;
// 找二維矩陣中<=mid的元素總個數(shù)
int count = findNotBiggerThanMid(matrix, mid, row, col);
if (count < k) {
// 第k小的數(shù)在右半部分炒事，且不包含mid
left = mid + 1;
} else {
// 第k小的數(shù)在左半部分，可能包含mid
right = mid;
}
}
return right;
}
private int findNotBiggerThanMid(int[][] matrix, int mid, int row, int col) {
// 以列為單位找蔫慧，找到每一列最后一個<=mid的數(shù)即知道每一列有多少個數(shù)<=mid
int i = row - 1;
int j = 0;
int count = 0;
while (i >= 0 && j < col) {
if (matrix[i][j] <= mid) {
// 第j列有i+1個元素<=mid
count += i + 1;
j++;
} else {
// 第j列目前的數(shù)大于mid挠乳，需要繼續(xù)在當(dāng)前列往上找
i--;
}
}
return count;
}
