剑指offer-二维数组中的查找

题目描述

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

分析

第一反应就是对每一行进行二分查找,并对元素是不是会在这一行可以做一个初步的判断。这样复杂度是O(mlogn)

但是,显然这样并没有用到列也是顺序增长的条件,所以好的办法是从左下角开始,如果target比当前的数要大,那一定在上一行,如果比当前的数要下,那么一定在下一列,由此方案查找.这样复杂度是O(m+n).

代码

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int rows = array.size();
for(int i=0;i<rows;i++){
int min_index = 0;
int max_index = array[i].size()-1;
if(max_index>=0 && target>=array[i][0] && target<=array[i][max_index]){
while(min_index<=max_index){
int middle_index = (min_index+max_index)/2;
if(array[i][middle_index]<target){
min_index = middle_index+1;
}else if(array[i][middle_index]>target){
max_index = middle_index-1;
}else{
return true;
}
}
}
}
return false;
}
};

更好的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int rows = array.size();
if(rows==0 || array[0].size()==0){
return false;
}
int x = rows-1;
int y = 0;
while(true){
if(array[x][y]>target){
x = x - 1;
}else if(array[x][y]<target){
y = y + 1;
}else{
return true;
}
if( x<0 || y>=array[x].size()){
return false;
}
}
}
};