题目链接：有序矩阵中第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; } }