74. 搜索二維矩陣
https://leetcode-cn.com/problems/search-a-2d-matrix/
難度：中等
題目：
編寫一個(gè)高效的算法來判斷m x n矩陣中百炬，是否存在一個(gè)目標(biāo)值。該矩陣具有如下特性：
每行中的整數(shù)從左到右按升序排列。
每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)贿讹。
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
示例：
示例 1：
輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
輸出：true
示例 2：
輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
輸出：false
分析：
凡是能通過暴力AC的題都不能算中等題...
這道題分別用暴力篮绿、貪心、二分完成
解題1.雙層for循環(huán)：
class Solution:
def searchMatrix(self, matrix, target):
for i in matrix:
for j in i:
if j == target:
return True
elif j > target:
return False
return False
解題2.貪心算法：
class Solution:
def searchMatrix(self, matrix, target):
line = len(matrix) - 1
row = len(matrix[0]) - 1
i = j = 0
while True:
if matrix[i][j] == target:
return True
elif i < line and matrix[i + 1][j] <= target:
i += 1
elif j < row and matrix[i][j + 1] <= target:
j += 1
else:
return False
解題3.二分查找：
class Solution:
def searchMatrix(self, matrix, target):
line = len(matrix)
row = len(matrix[0])
left = 0
right = line * row
while left < right:
i, j = divmod((left + right) // 2, row)
if matrix[i][j] == target:
return True
if matrix[i][j] < target:
left = i * row + j + 1
else:
right = i * row + j
return False
歡迎關(guān)注我的公眾號(hào): 清風(fēng)Python齐唆，帶你每日學(xué)習(xí)Python算法刷題的同時(shí)拧烦，了解更多python小知識(shí)。有喜歡力扣刷題的小伙伴可以加我微信互相鼓勵(lì)莉擒，共同進(jìn)步酿炸，一起玩轉(zhuǎn)超級(jí)碼力！
我的個(gè)人博客：https://qingfengpython.cn
