题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

知识点

数组；查找

Qiang的思路

通过对问题的分析，我发现题目中的二维数组具有如下的特点：

左上角元素为整个数组中的最小值。
右下角元素为整个数组中的最大值。

对于该问题通过遍历的方法肯定是可以得到结果的。但是如果通过这种方法去做这个题就没有什么意义了。所以肯定有更加高效的算法等待着我们去发现。

再进一步思考，想要简化时间复杂度，必须能够大幅度的降低问题的搜索空间才行。判断整数的存在与否的关键在于大小的判断，那这个过程中必然出现小于或者是大于的情况，那么可以通过这个角度出发去降低问题的搜索空间。

可以发现，二维数组右上角的元素具有非常良好的特性，因为它比其左侧的元素都大，比其右侧的元素都小。所以如果对其进行判断的时候发现目标整数值大于右上角的元素值，那么肯定大于二维数组第一行所有的元素，这种情况下该行元素便可以完全删除。

相反，当目标整数值小于二维数组右上角的元素时，整个数组最后一列元素也就没有了比较的价值，可以被删除。这样一次比较便可以将整个搜索空间减少一次。

当右上角的元素等于目标整数时便找到了该整数，如果当二维数组被删减为空了还没有找到就说明该数组中不存在该整数。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if array==[] or array[0]==[]:
            return False
        if array[0][-1]==target:
            return True
        if array[0][-1]<target:
            return self.Find(target, array[1:])
        if array[0][-1]>target:
            return self.Find(target, [a[:-1] for a in array])

在该代码中应该注意python对二维数组的操作，不像C/C++，在不使用numpy等库的时候，python对二维数组的操作相对复杂一些，在这里借助了for循环才实现了对列的删减。

另外，在判断数组是否为空的时候存在两个条件，这是因为当按行删减时，最后的数组为[]，如果按列删减最后的数组应该是这样的[[],[],...,[]]。并且因为or的短路原则，所以这样写也不会因为判断[]的第0号位置而出错。

时间复杂性分析

最坏的情况下，该算法需要将所有的行和列都删除一遍，时间复杂度为O(n+m)，n为行数，m为列数。也就是线性的时间复杂度，但是遍历将会是O(nm)，平方级别的复杂度。所以该算法肯定是搞笑的。该代码首先需要得到一个全为False的flag数组，时间复杂度为O(n)。然后通过遍历的方式去判断是否当前的数为重复出现的数，时间复杂度为O(n)。综上，时间复杂度为O(n)。