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

示例：

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

返回 13。

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

首先最简单的思路就是，先把矩阵转成一维数组，然后对数组进行排序，最后返回下标为k-1的数即可，时间复杂度是$O(n^2{\log }_{2}n)$，空间复杂度为$O(n^2)$由于题中提醒行列都是按顺序递增的，所以可以采用二分查找，矩阵左斜对角线两端即为最小和最大值，然后以中间值来划分，若左侧值包含了大于等于K个数据，那么将区间缩小在左区间寻找，否则在右区间进行寻找，直到最后左右两端值相等为止。

然后计算左侧中包含的数据个数如何计算呢？ 例如中间值=8为例， 我们以初始值比较在matrix的左下角，i = n-1,j=0开始，当比较matrix[i][j]<=mid值时，就将此时当前列的小于等于mid的数统计进总数，如果大于mid值,则i–考虑上一行是否小于或等于mid,统计完当前列，则j++统计下一列，直到所有列被统计完，这样走统计只需N步（即矩阵的行数或列数）。 时间复杂度是$O(Nlo{g}_2(r-l))$，其中统计个数是$O(N)$，r,l即矩阵右下角和左上角的值。

class Solution { public: bool haveKth(vector<vector<int>>& matrix,int k,int mid) { int num = 0; int n = matrix.size(); int i = n-1; int j = 0; while(i >=0 && j < n ) { if(matrix[i][j] <= mid) { num += i+1; j++; } else { i--; } } return num>=k; } int kthSmallest(vector<vector<int>>& matrix, int k) { int n = matrix.size(); int left=matrix[0][0],right=matrix[n-1][n-1]; while(left<right) { int mid = (left + right)/2; if(haveKth(matrix,k,mid)) { right = mid; } else { left = mid + 1; } } return left; } };