在一個二維數(shù)組中（每個一維數(shù)組的長度相同）褐奥，每一行都按照從左到右遞增的順序排序仰挣，每一列都按照從上到下遞增的順序排序冒冬。請完成一個函數(shù)伸蚯，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)简烤。
時間限制：1秒 空間限制：32768K
偶劣剩客網(wǎng) 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 （張學(xué)志）: 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都是調(diào)用python標(biāo)準(zhǔn)庫函數(shù)挥萌，底層實現(xiàn)是一樣的。
方法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改進版遍歷到第一個相同目標(biāo)元素就break了。在這種特殊情況下榨馁，方法2改進版會稍微快一點憨栽。顯然，這兩種方法都沒有利用題目所示的二維數(shù)組的性質(zhì)：
- 每個一維數(shù)組長度相同翼虫；
- 從左至右屑柔，從上至下遞增。
方法3 （張學(xué)志）：利用題中數(shù)組的特性
| table | ||
|---|---|---|
| A | B | C (start) |
| D | E | F |
| F (stop) | G | H |
假設(shè)有兩個指針珍剑，分別是行和列掸宛，從右上角開始遍歷，
如果target<C招拙，則target<列{CFH}旁涤，列指針左移到B;
如果target<B翔曲，列指針繼續(xù)左移，反之劈愚，則行指針下移。
如果target>C闻妓，則target>行{ABC}菌羽，行指針下移到F；
如果target<F由缆，列指針左移注祖，反之，行指針繼續(xù)下移均唉。
有點暈是晨？
- 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 |
時間復(fù)雜度對比 （對于m行*n列的數(shù)組）
| 方法 | 大O |
|---|---|
| 方法1 | m*n |
| 方法2 | m*n |
| 方法3 | m+n-1 |
總結(jié)
題目本身不限制語言的罩缴，應(yīng)該是希望coder考慮時空復(fù)雜度以及數(shù)組本身的特性。如果選擇用python层扶，那么方法2改進版應(yīng)該是最pythonic的寫法箫章，簡單易懂。具體選擇什么方法取決于現(xiàn)實數(shù)據(jù)量的大小镜会。如果真的要極致的performance檬寂，還是用C吧，哈哈戳表。
