在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
时间限制：1秒 空间限制：32768K
牛客网 Online Test

方法 1（我第一感觉的写法，好瓜啊）: list.count(target)

class Solution:
    def Find(self, target, array):
        for i in range(len(array)):
            if array[i].count(target)>0:
                return True
        return False

time (ms)	memory (kB)
443	6060

方法 2 （张学志）: if target in list

class Solution:
    def Find(self, target, array):
        flag = False
        for index in range(len(array)):
            if target in array[index]:
                flag = True
        return flag

time (ms)	memory (kB)
438	6044

方法1和方法2都是调用python标准库函数，底层实现是一样的。

方法2改进版：

class Solution:
    def Find(self, target, array):
        for index in range(len(array)):
            if target in array[index]:
                return True
        return False

time (ms)	memory (kB)
403	5880

如果在array中有好几个和target一样的元素，方法1和方法2都可能遍历到每个相同元素，而方法2改进版遍历到第一个相同目标元素就break了。在这种特殊情况下，方法2改进版会稍微快一点。显然，这两种方法都没有利用题目所示的二维数组的性质：

• 每个一维数组长度相同；
• 从左至右，从上至下递增。

方法3 （张学志）：利用题中数组的特性

table
A	B	C (start)
D	E	F
F (stop)	G	H

假设有两个指针，分别是行和列，从右上角开始遍历，
如果target<C，则target<列{CFH}，列指针左移到B;
如果target<B，列指针继续左移，反之，则行指针下移。

如果target>C，则target>行{ABC}，行指针下移到F；
如果target<F，列指针左移，反之，行指针继续下移。

有点晕？

• start：右上
• target<element，列指针-- （左移）
• target>element，行指针++（下移）
• stop：左下

举个实例

table
1	2	8
3	4	9
9	10	12

target=7
1	(step 2) 7>2	(step 1) 7<8
3	(step 3) 7>4	9
(step 5) 7<9 (stop)	(step 4) 7<10	12

不存在

target=10
1	2	(step 1) 10>8
3	7>4	(step 2) 10>9
9	(step 4) 10==10 (stop)	(step 3) 10<12

存在

class Solution:
   def Find(self, target,array ):
       nrow = len(array)
       ncol = len(array[0])
       row = 0
       col = ncol-1
       while row<nrow and col>=0:
           if target == array[row][col]:
               return True
           elif target > array[row][col]:
               row += 1
           else:
               col -= 1
       return False

time (ms)	memory (kB)
182	5728

时间复杂度对比 （对于m行*n列的数组）

方法	大O
方法1	m*n
方法2	m*n
方法3	m+n-1

总结

题目本身不限制语言的，应该是希望coder考虑时空复杂度以及数组本身的特性。如果选择用python，那么方法2改进版应该是最pythonic的写法，简单易懂。具体选择什么方法取决于现实数据量的大小。如果真的要极致的performance，还是用C吧，哈哈。

参考

python list 函数