当前位置: 首页> 游戏> 评测 > 中建八局第一建设有限公司税号_微分销系统bh_今日头条新闻最全新消息_搜外网

中建八局第一建设有限公司税号_微分销系统bh_今日头条新闻最全新消息_搜外网

时间:2025/7/12 0:08:36来源:https://blog.csdn.net/qq_45791939/article/details/146402249 浏览次数:0次
中建八局第一建设有限公司税号_微分销系统bh_今日头条新闻最全新消息_搜外网

原题链接:Leetcode 378. 有序矩阵中第 K 小的元素

解题思路:

参考自博客:LeetCode题练习与总结:有序矩阵中第 K 小的元素–378

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

为什么left一定在矩阵中?

  • 循环过程中,矩阵中第k小的那个数始终在区间[left, right]中

  • 循环过程中,left和right可能不是矩阵中的元素,但是[left, right]中某个元素 ”在矩阵中“ 且 ”满足第k小“

  • 当right == left时,[left, right]中只有一个元素了(即left),所以此时left必然 ”在矩阵中“ 且
    ”满足第k小“

此题的完整流程+过程演示:

#include <iostream>
#include <vector>
using namespace std;int kthSmallest(vector<vector<int>>& matrix, int k) {int n=matrix.size();int l=matrix[0][0];int r=matrix[n-1][n-1];int round=1;while(l<r){cout<<"第" <<round<<"次查找:"<<endl;cout<<"开始时:" <<endl;int mid=l+(r-l)/2;int j=n-1;int cnt=0;cout<<"left:"<<l<<endl;cout<<"right:"<<r<<endl;cout<<"mid:"<<mid<<endl;for(int i=0;i<n;i++){while(j>=0 && matrix[i][j]>mid){j--;}cnt+=(j+1);}if(cnt<k){l=mid+1;}else{r=mid;}round++;cout<<"找到" <<cnt<<"个小于等于mid的数"<<endl;cout<<"更新后:"<<endl;cout<<"left:"<<l<<endl;cout<<"right:"<<r<<endl;cout<<"------------------------------------------------------"<<endl;}return l;
}int main()
{vector<vector<int>> mat;mat.push_back({1,5,9});mat.push_back({10,11,13});mat.push_back({12,13,15});int res=kthSmallest(mat, 8);cout<<res<<endl;return 0;
}
1次查找:
开始时:
left:1
right:15
mid:8
找到2个小于等于mid的数
更新后:
left:9
right:15
------------------------------------------------------2次查找:
开始时:
left:9
right:15
mid:12
找到6个小于等于mid的数
更新后:
left:13
right:15
------------------------------------------------------3次查找:
开始时:
left:13
right:15
mid:14
找到8个小于等于mid的数
更新后:
left:13
right:14
------------------------------------------------------4次查找:
开始时:
left:13
right:14
mid:13
找到8个小于等于mid的数
更新后:
left:13
right:13
------------------------------------------------------
13
关键字:中建八局第一建设有限公司税号_微分销系统bh_今日头条新闻最全新消息_搜外网

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: