Leetcode 378. 有序矩阵中第K小的元素

题目

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

示例：

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

提示：

你可以假设 k 的值永远是有效的，1 ≤ k ≤ n² 。

题解

二分查找 显然我们是在[matrix[0][0],matrix[m-1][n-1]]找到一个数，它是第k小的数，满足递增关系，因此我们可以使用二分查找。 我们确定mid时，需要找小于mid的数的个数，这里又可以对每行使用二分查找，找到小于mid数的个数，每行的结果累加就是小于这个数的所有个数了。如果cnt<k,我们要找的数就可能在[mid,r]上，为什么不是mid+1呢，因为mid可能有多个；如果cnt>=k,我们要找的数就是[l,mid]上，我们把答案放在l上，那么我们就令r=mid-1。 详细过程见代码

代码

int kthSmallest(vector<vector<int>>& matrix, int k) { int m=matrix.size(),n=matrix[0].size(); int small=matrix[0][0],big=matrix[m-1][n-1],mid; while(small<big){ mid = (small+big)/2 + 1; int cnt = 0; for(int i=0; i<m; i++){ //统计小于mid的数的个数 int l=0,r=n-1; while(l <= r){ int midC = (l+r)/2; if(matrix[i][midC] < mid) l = midC+1; else r = midC - 1; } cnt += l; } if(cnt < k) small = mid; else big = mid-1; } return small; }

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