题目描述
在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
样例
输入数组:
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
如果输入查找数值为7,则返回true,
如果输入查找数值为5,则返回false。
算法
ps:这是小弟第一次写题解,有问题的地方请多包涵
这个二维数组是升序排列,从上自下或者从左自由都是递增
所以我们可以单调的从小到大的找,先按行遍历,遇见比target大的数立即返回
相等则返回true
一行遍历结束没有找到即跳到下一行
当第一行的array[i][0]都大于target时,说明它后面的数都大于target
直接返回false
时间复杂度分析:有m行n列,所以最坏的情况下是o(mn);
以1s的时间来说没有问题,这个方法很low
但是我觉得是最直接最容易理解的一种(苦笑)
C++ 代码
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
if(array.empty()||array[0].empty())
return false;
for(int i=0;i<array.size();i++){
if(array[i][0]>target){//判断行是否大于target
return false;
}
for(int j=0;j<array.size();j++){//判断列是否大于target
if(array[i][j]==target)
return true;
if(array[i][j]>target)//大于即可返回
break;
}
}
}
};