给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。 示例： matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, 返回 13。
分析： i)利用矩阵的特点：其中每行和每列元素均按升序排序。 由这个特点可以得到几个性质： 1.A是四个元素中最小值，D是最大值。 2.如果C>n,则D一定大于n，此时如果A<n,则B小于n。也就是说，当我们判断完C大于n后，想要找到下一个小于等于n的元素，应该先判断A的情况；同理，判断完C小于等于n后，应该先判断D的情况。 3.C小于等于n时，C所在的那一列，C以上的元素都是小于等于n的。
根据上面的总结从一个矩阵的左下角元素开始，按照2的规则： 如果当前元素≤n，则把这一列中到当前元素的个数进行累加，然后判断右边的元素； 如果当前元素>n，就判断上边的元素； 一直遍历到右上角，就可以得到矩阵中所有小于等于n的元素个数。
ii)利用小于等于mid的元素个数进行二分查找 把矩阵想象成下图的序列：最小值和最大值是确定的，中间不是具体的元素，而是一个范围。 当序列中小于等于mid的元素个数小于k时，则第k小的元素肯定在[mid+1，right]中找到； 当序列中小于等于mid的元素个数大于等于k时，则第k小的元素肯定在[left，mid]中找到；
在二分查找中需要注意“=”到底归在哪边的问题： 当left=i，right=i+1时，mid=left ①num<mid, right = mid-1; num≥mid, left=mid。 这时，如果num<mid, right= left-1,两个边界不会相交，无法得到正确结果；如果num≥mid，left= left，会陷入死循环。 ②num≤mid, right = mid; num＞mid, left=mid+1。 这时，如果num<mid, right= left；如果num≥mid，left= right，无论是哪种情况，left和right都会相交。
class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { int left = matrix[0][0],right = matrix[matrix.size()-1][matrix[0].size()-1]; int mid; while(left<right){ mid = left+(right-left)/2;//防止溢出 if(lessThanK(matrix,k,mid)) left = mid+1; else right= mid; } return left; } bool lessThanK(vector<vector<int>>& matrix, int k,int mid){ int row = matrix.size()-1,col = 0; int sum = 0; while(row>=0&&col<matrix[0].size()){ if(matrix[row][col]<=mid){ sum+= row+1; col++; }else row--; } if(sum<k)return true; else return false; } };