在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
时间限制：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吧，哈哈。
