题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
解法一
每一行递增，每一列也递增，于是从二维数组的右上角开始比较，每次都比较这一行最大的，如果target比这一行最大的还大，那这一行肯定没有目标值，直接跳入下一行。如果比这一行最大的小，则这一列肯定没有目标值。每一次比较都砍掉一行或一列。复杂度o(m+n)
class Solution
{
public:
bool Find(
int target, vector<vector<
int>>
array)
{
for (
int i =
0, j = array[
0].size() -
1; i < array.size() && j >=
0;)
{
if (target ==
array[i][j])
return true;
if (target <
array[i][j])
{
j--
;
continue;
}
if (target >
array[i][j])
{
i++
;
continue;
}
}
return false;
}
};
解法二：
对每一行都进行二分查找 复杂度(nlogn)
class Solution
{
public:
bool Find(
int target, vector<vector<
int>>
array)
{
for (
int i =
0; i < array.size(); i++
)
{
int beg =
0;
int end = array[i].size() -
1;
while (beg <=
end)
{
int mid = (beg + end) /
2;
if (target ==
array[i][mid])
return true;
else if (target >
array[i][mid])
beg = mid +
1;
else
end = mid-
1;
}
}
return false;
}
};
转载于:https://www.cnblogs.com/ruoh3kou/p/10042249.html
相关资源：数据结构—成绩单生成器
