【剑指offer】二维数组中的查找☆
2024-09-03 14:24:05
题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
自己的思路实在是傻×了，先看下正确思路吧
把当前数字定位在第一行，最后一列。如果数字小则增大行，如果数字大则减小列！O(M+N)
bool Find3(vector<vector<int> > array,int target)
{
if(array.empty() && array[].empty())
return false; int r = , c = array[].size() - ;
while(r < array.size() && c >= )
{
if(array[r][c] == target)
return true;
else if(array[r][c] > target)
c--;
else
r++;
}
return false;
}
我自己二分查找的思路，每次扔掉一半O(log(MN)),超级繁琐，也AC了
bool Find(vector<vector<int> > array,int target) {
if(array.empty() && array[].empty())
return false;
//用四个变量标记剩余的查找范围
int cleft = , cright = array[].size() - ;
int rup = , rdown = array.size() - ;
int l, r, u, d;
while(cleft <= cright && rup <= rdown)
{
//对限定区域的第一行进行二分查找，定位刚好小于target值的列
l = cleft, r = cright;
if(array[rup][l] > target) //所有的都大于target
return false;
else
{
while(l <= r)
{
int m = l + (r - l) / ;
if(array[rup][m] == target)
return true;
else if(array[rup][m] < target)
l = m + ;
else
r = m - ;
}
cright = r;
}
//对限定区域的第一列进行二分查找，定位刚好小于target值的行
u = rup, d = rdown;
if(array[u][cleft] > target) //所有的都大于target
return false;
else
{
while(u <= d)
{
int m = u + (d - u) / ;
if(array[m][cleft] == target)
return true;
else if(array[m][cleft] < target)
u = m + ;
else
d = m - ;
}
rdown = d;
}
//对限定区域的最后一行进行二分查找，定位刚好大于target值的列
l = cleft, r = cright;
if(array[rdown][r] < target) //所有的都小于target
return false;
else
{
while(l <= r)
{
int m = l + (r - l) / ;
if(array[rdown][m] == target)
return true;
else if(array[rdown][m] < target)
l = m + ;
else
r = m - ;
}
cleft = l;
}
//对限定区域的最后一列查找，定位刚好大于target值的行
u = rup, d = rdown;
if(array[d][cright] < target) //所有的都小于target
return false;
else
{
while(u <= d)
{
int m = u + (d - u) / ;
if(array[m][cright] == target)
return true;
else if(array[m][cright] < target)
u = m + ;
else
d = m - ;
}
rup = u;
}
}
return false; //没找到
}
最新文章
- Shell入门教程：流程控制（1）命令的结束状态
- js模版引擎handlebars.js实用教程——为什么选择Handlebars.js
- hdu 1978 How many ways
- How to: Host and Run a Basic Windows Communication Foundation Service
- Android Training精要（六）如何防止Bitmap对象出现OOM
- java基于xml配置的通用excel单表数据导入组件(五、Action处理类)
- C的printf与scanf的用法
- android 66 sharedperference的使用
- Amoeba实现mysql主从读写分离
- m2eclipse简单使用,创建Maven项目 ,运行mvn命令(转)
- Android线程之Thread 、Runnable 的两个例子
- C/C++学习路线图
- Lazyman功能实现
- MongoDB--初始
- HDU 2203 亲和串(KMP)
- Rust语言
- 【原创】运维基础之OpenResty(Nginx+Lua)+Kafka
- MySQL 5.6 (Win7 64位)下载、安装与配置图文教程
- Nginx/Apache之伪静态设置 - 运维小结
- Gerrit日常维护记录