题目
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例一
输入: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
示例二:
输入: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 = 20
输出:false
提示:
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^9 <= matrix[i][j] <= 10^9
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9
思路:
思路一:
暴力解法,直接两层循环遍历,可行原因,m,n较小,O(mn)的时间复杂度并不大。
思路二:
对每行进行遍历,采用二分法进行行遍历(行有序),注意遍历前可以特判,若行首比目标还大,说明此后的所有行都会比目标值大,结束遍历返回false,若行尾比目标值还小说明当前行肯定都比目标小,不需要遍历改行,直接contine,若特殊情况都不满足,则对改行进行二分查找。
思路三:
巧妙的从右上角进行遍历,若当前值大,则往左移动一位,若当前值小,则往下移动一位。
代码
思路一
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
n = len(matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j]==target:
return True
return False
思路二
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
def serachdata(matrixline:List[int],target:int) -> bool:
n = len(matrixline)
l = 0
r = n-1
while(l<=r):
mid = (l+r)//2
if(matrixline[mid]>target):
r =mid-1
elif matrixline[mid]<target:
l = mid+1
elif matrixline[mid]==target:
return True
return False
m = len(matrix)
n = len(matrix[0])
for i in range(m):
if(matrix[i][-1]<target):
continue
if matrix[i][0]>target:
break
if serachdata(matrix[i],target):
return True
return False
思路三
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
n = len(matrix[0])
i = 0
j = n-1
while(i<m and j>=0):
if matrix[i][j]==target:
return True
elif matrix[i][j]>target:
j -=1
else: i+=1
return False
标签:遍历,return,matrix,int,List,II,240,热题,target
From: https://www.cnblogs.com/anamzingclown/p/17615462.html