题目链接：有序矩阵中第K小的元素
题目描述：
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

返回 13。

提示：
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

题目分析：最简单粗暴的直接排序然后取第K个，当然，仍然可以用堆来求解topk问题（维护一个大小为K的大顶堆），但是仍然不是最优解。由于题目中涉及到有序序列，自然想到用二分的思想去做，这个二维矩阵的左上角和右下角一定分别是整个序列最小值、最大值，这确定了我们二分的上下界。每次二分我们通过统计mid左边（即小于等于mid）的数的个数cnt，与k比较，如果小于k，证明找的这个mid值偏小了，答案一定要比mid大，因此增大下界，否则就减小上界。直到下界大于等于上界。其实就是通过二分不断的去逼近这个k值，找到一个mid值的cnt等于k的数。
至于如何统计这个cnt，同样的利用这个矩阵的特点，从矩阵的右上角开始判断，小于mid则直接累加本行个数，因为这个数已经是这行最大的数了，否则就向左走，看代码吧：

class Solution {public int kthSmallest(int[][] matrix, int k) {int n = matrix.length;int l = matrix[0][0], r = matrix[n-1][n-1];while(l < r){int i = 0,j = n-1,sum = 0,mid = (l+r)/2;while(i < n && j >= 0){//统计个数if(matrix[i][j] <= mid){//累加本行个数sum += j+1;++i;}else --j;//向左走}// System.out.println(sum+": "+mid);if(sum >= k) r = mid;//减小上界else l = mid+1;//增大下界}return l;}
}

体会思想吧。。。

这里补充一个题，用的就是统计个数部分的思路

搜索二维矩阵

根据矩阵特点找到一个合适的搜索起点就行了，这个起点满足往不同方向走会有不同的单调性，因此可以在很低的时间复杂度内找到值

代码：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrix.length==0) return false;int m = matrix.length;int n = matrix[0].length;int i = 0,j = n - 1;//从右上角开始走while(i < m&&j >= 0){if(matrix[i][j]==target) return true;if(matrix[i][j]>=target)j--;//大了，往递减走else i++;//否则往递增走}return false;}
}