378. 有序矩阵中第K小的元素(排序或者二分)
2021-05-03 22:30
阅读:698
标签:排序 load 图片 -- 二维 href 二维矩阵 kth cto
378. 有序矩阵中第K小的元素
-
第一种方法:将二维矩阵中的数存起来,然后排序输出第k个,耗时较多
class Solution {
public:
int kthSmallest(vector>& matrix, int k) {
vectorv;
for(int i=0;i
-
第二种方法:利用二分,左上角的数最小,右下角的数最大,取个mid,然后在矩阵中找出小于等于mid的数cnt
-
如果cnt
-
当cnt>=k的时候,说明小于等于mid的数已经超过k了,mid比我们要求的数肯定大,那么将右端点为mid即可,在左边查找。
-
至于怎么找矩阵中小于等于mid的个数,我们可以从矩阵左下角开始找,当该位置的数
就是该列第i行的上面的所有的元素都小于等于mid,累加即可,同时列指针j++;
如果该位置的数大于了mid,那么只要将行指针向上i--即可。复杂度比第一种方法小得多,耗时短。
class Solution {
public:
bool check(vector>& matrix,int mid,int k)
{
int n=matrix.size();
int i=n-1,j=0;
int cnt=0;
while(i>=0&&j>& matrix, int k) {
int n=matrix.size();
int L=matrix[0][0],R=matrix[n-1][n-1];
while(L>1;
if(check(matrix,mid,k))
L=mid+1;
else
R=mid;
}
return L;
}
};
378. 有序矩阵中第K小的元素(排序或者二分)
标签:排序 load 图片 -- 二维 href 二维矩阵 kth cto
原文地址:https://www.cnblogs.com/Vampire6/p/13196377.html
文章来自:搜素材网的编程语言模块,转载请注明文章出处。
文章标题:378. 有序矩阵中第K小的元素(排序或者二分)
文章链接:http://soscw.com/index.php/essay/82000.html
文章标题:378. 有序矩阵中第K小的元素(排序或者二分)
文章链接:http://soscw.com/index.php/essay/82000.html
评论
亲,登录后才可以留言!