Leetcode 74. 搜索二维矩阵 C+
2024-09-05 22:39:04
二分法，先对行二分找出结果可能存在的行，再对这一行二分查找。O(Log m+Log n)，m、n分别为矩阵的高和宽。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
//二分，先找可能存在的行，再在行里二分找数
if(matrix.empty() or matrix[].empty()){return false;}
int m=matrix.size(),n=matrix[].size();
int row_le=,row_ri=m-,row_mi;
while(row_le<row_ri){
row_mi=row_le+(row_ri-row_le)/;
if(matrix[row_mi][]>target){
row_ri=row_mi;
}
else if(matrix[row_mi][n-]<target){
row_le=row_mi+;
}
else{
row_le=row_ri=row_mi;
}
}
int le=,ri=n-,mi;
while(le<ri){
mi=le+(ri-le)/;
if(matrix[row_le][mi]<target){
le=mi+;
}
else{
ri=mi;
}
}
return matrix[row_le][le]==target;
}
};
评论区的：O(m+n)， m、n分别为矩阵高和宽，更简洁，尽管牺牲了复杂度。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target)
{
if(matrix.size()== or matrix[].size()==)
{
return false;
}
int m=matrix.size(),n=matrix[].size();
int row=,col=n-;
while(row<m and col>=)
{
if(matrix[row][col]==target)
{
return true;
}
else if(matrix[row][col]>target)
{
--col;
}
else
{
++row;
}
}
return false;
}
};
最新文章
- Linux编译源码的方式安装Qt4开发环境（基于Ubuntu系统）
- Objective-C如何对内存管理的?
- sqlserverJDBC驱动链接
- 'Could not load NIB in bundle: 'NSBundle xxx/storeFlix.app> ' with name 'UIViewController-w6Q-ra-j06' and directory 'StoreFlixIpad.storyboardc
- HBase 实战(1)--HBase的数据导入方式
- 网络流(最大流) POJ 1637 Sightseeing tour
- Intellij Idea 12 加载weblogic8X的插件
- 模拟Spring依赖注入
- linux下面安装配置mongoDB
- 理解JavaScript原型
- Install Centrifugo and quick start
- Spring Boot 2.0 的快速入门（图文教程）
- oracle追加表空间
- css 清除浮动的几种方式
- django 网站的搭建（2）
- 1.2、CDH 搭建Hadoop在安装之前(CDH基于包的安装所需的权限)
- 自己在完第一遍STL和Directx 9.0 游戏开发编程基础书后的体会
- How to execute sudo command in remote host via SSH
- 洛谷 P1347 排序
- Ubuntu-18.04 下修改root用户密码，安装SSH服务，允许root用户远程登录，安装vsftp服务器