378. 有序矩阵中第K小的元素（排序或者二分）

2021-05-03 22:30

阅读：609

标签：排序 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

上一篇：Java | 顶层类（Top-Level Class）

下一篇：python 列表(List)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：378. 有序矩阵中第K小的元素（排序或者二分）
文章链接：http://soscw.com/index.php/essay/82000.html

亲，登录后才可以留言！

378. 有序矩阵中第K小的元素（排序或者二分）

第一种方法：将二维矩阵中的数存起来，然后排序输出第k个，耗时较多

第二种方法：利用二分，左上角的数最小，右下角的数最大，取个mid，然后在矩阵中找出小于等于mid的数cnt

如果cnt

当cnt>=k的时候，说明小于等于mid的数已经超过k了，mid比我们要求的数肯定大，那么将右端点为mid即可，在左边查找。

至于怎么找矩阵中小于等于mid的个数，我们可以从矩阵左下角开始找，当该位置的数

就是该列第i行的上面的所有的元素都小于等于mid，累加即可，同时列指针j++;

如果该位置的数大于了mid，那么只要将行指针向上i--即可。复杂度比第一种方法小得多，耗时短。

评论

热门文章

推荐文章

最新文章

置顶文章