題目
在一個 n * m 的二維數(shù)組中款侵，每一行都按照從左到右遞增的順序排序躏结，每一列都按照從上到下遞增的順序排序潜的。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)永部，判斷數(shù)組中是否含有該整數(shù)独泞。
示例:
現(xiàn)有矩陣 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
給定 target = 5，返回 true苔埋。
給定 target = 20懦砂，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
注意：本題與主站 240 題相同：https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有组橄。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)荞膘，非商業(yè)轉(zhuǎn)載請注明出處。
解法
動態(tài)規(guī)劃
最容易想到的就是動態(tài)規(guī)劃玉工。
class Solution:
def __init__(self):
self.ans = False # 類似全局變量
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
# 怎么想也是一個動態(tài)規(guī)劃的題目
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
self.naive_walk(matrix,target,0,0)
return self.ans
# 超時
def naive_walk(self, matrix,target,i,j):
if i>=len(matrix) or j >=len(matrix[0]):
return
if self.ans == True:
return
n = matrix[i][j]
if target == n:
self.ans = True
return
if n > target:
return
self.naive_walk(matrix,target,i,j+1)
self.naive_walk(matrix,target,i+1,j)
然而這個超時了羽资，主要的問題是復(fù)雜度為m*n.
從右上角開始
要充分利用數(shù)組的順序，每一行都按照從左到右遞增的順序排序遵班，每一列都按照從上到下遞增的順序排序屠升。
從左上角開始選擇的話潮改，需要回溯很多次。但是從右上角開始的話腹暖，如果當前值比較小的話汇在，就往下，當前值比較大的話微服，就往左趾疚。甚至不需要回溯就能完成。
遞歸版本和非遞歸版本：
class Solution:
def __init__(self):
self.ans = False
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
# 怎么想也是一個動態(tài)規(guī)劃的題目
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
self.walk_right(matrix,target,0,len(matrix[0])-1)
# self.ans = self.easy_walk(matrix,target)
return self.ans
def walk_right(self, matrix,target, i, j):
if i >= len(matrix) or j < 0:
return
#print(i,j)
num = matrix[i][j]
if num == target:
self.ans = True
return
if num < target:
self.walk_right(matrix,target,i+1,j)
else:
self.walk_right(matrix,target,i,j-1)
def easy_walk(self, matrix,target):
if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0:
return False
i = 0
j = len(matrix[0])-1
while i<len(matrix) and j >=0 :
num = matrix[i][j]
if num == target:
return True
if num > target:
j -= 1
if num < target:
i += 1
return False
總結(jié)
這一題主要是想到了從右上角開始的思路就好了以蕴。
** 踩過的坑 **
如果寫成這樣：
if matrix[i][j] > target: j -= 1
if matrix[i][j] < target: i += 1
if matrix[i][j] == target: return True
這樣在i+1或者j-1的時候已經(jīng)越界了糙麦，還去取值會出錯！
同時丛肮，有時候i j 已經(jīng)偏移了赡磅，這時候取得的 matrix[i][j] 不是當前要判斷的值。
