一、题目描述
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
输入数组:
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
如果输入查找数值为10,则返回true,
如果输入查找数值为5,则返回false。
我们一步一步的挖掘题目的精髓,寻找一个优秀的解法
(1)根据题目的描述,很容易想到暴力解法。那太low了。
(2)再仔细观察二维数组的特点,每行每列都是递增的,那么可以使用逐行(或逐列)二分法查找的方法呀,比方法(1)优秀一些,但是好像也只是利用行或列的递增,并没有将二者结合起来。
(3)因此引出了,最终版的解法(单调性扫描法)。
接下来用图的方式清晰的讲解其原理
假设输入数组:
假设输入的查找数值为 target=10:
通过将target=10 与 “每一行”的最后一个数字(9),进行比较的方式依次进行。
no pic u say a J8
好的接下来看图
因为行(i)从左到右是递增的关系,列(j)从上到下是递增关系,因此,利用这个单调性可以这种去操作:
每次都利用target与数组的右上角的数进行比较
(1)第一轮比较过程
如果 target=10,大于数组a[0][3]=9(第一行最大值),那么第一行的所有数都不满足要求。
直接查找下一行 ==> i++
(2)第二轮比较过程
target=10,与a[1][3]=12(最后一列的最小值)进行比较,此时target=10<12,那么这列的所有数必定都不满足要求。
直接查找前一列 ==> j--
(3)第三轮比较过程
target=10,与a[1][2]=9(当前行最大值)进行比较,此时target=10>9,那么这行的所有数必定都不满足要求。
直接查找下一行 ==> i++
是不是非常的清晰,而且效率极高,有效的利用了题目中提供的条件。
Python版
class Solution:
# array 二维列表
def Find(self, target, array):
if (len(array)==0 or len(array[0])==0):
return False
i=0
j=len(array[0])-1
while (i<len(array) and j>=0):
if array[i][j]==target:
return True
elif array[i][j]>target:
j -= 1
else:
i += 1
return False
C++版
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if (array.empty() || array[0].empty()) return false;
int i=0, j=array[0].size()-1;
while(i<array.size() && j>=0){
if (array[i][j]==target) return true;
if (array[i][j]>target) j--;
else i++;
}
return false;
}
};
每一步会排除一行或者一列,矩阵一共有 n 行,m 列,所以最多会进行 n+m步。所以时间复杂度是 O(n+m)。