【剑指Offer第一题】二维数组的查找
题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。成都创新互联公司是一家集网站建设,铁力企业网站建设,铁力品牌网站建设,网站定制,铁力网站建设报价,网络营销,网络优化,铁力网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。
注:设二维数组为m行n列。语言:C++
解法1:顺序查找
bool Find(int target, vector > array) {
vector >::iterator i;
vector::iterator j;
vector k;
for(i = array.begin(); i != array.end(); ++i)
{
k = *i;
for(j = k.begin(); j != k.end(); ++j)
{
if(*j == target)
return true;
}
}
return false;
}
时间复杂度O(mn),空间复杂度O(1)。
解法2:折半查找
bool Find(int target, vector > array) {
if(array.empty())
return false;
int row = array.size();
int col = array[0].size();
for(int i = 0; i < row; ++i)
{
if(array[i].empty())
return false;
int low = 0;
int high = col-1;
if(target == array[i][low])
return true;
if(target == array[i][high])
return true;
while(low <= high)
{
int mid = low + (high - low) / 2;
if(target == array[i][mid])
return true;
else if(target < array[i][mid])
high = mid - 1;
else
low = mid + 1;
}
}
return false;
}
时间复杂度O(mlogn),空间复杂度O(1)。
解法三:根据数组有序特性,从其右上角元素开始比较。
bool Find(int target, vector > array) {
if(array.empty())
return false;
int row = array.size();
int col = array[0].size();
int i = 0;
int j = col - 1;
while((i < row) && (j >= 0))
{
if(array[i].empty())
return false;
if(target == array[i][j])
return true;
else if(target < array[i][j])
j--;
else
i++;
}
return false;
}
时间复杂度O(m+n),空间复杂度O(1)
网站标题:【剑指Offer第一题】二维数组的查找
文章出自:http://scyanting.com/article/pscpip.html