《剑指offer》二维数组中的查找——巧妙解法
《剑指offer》二维数组中的查找——巧妙解法
一、题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
输入数组：
[
[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 FalseC++版
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)。