本文共 1008 字,大约阅读时间需要 3 分钟。
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Example:
Consider the following 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]]
Given target = 5
, return true
.
Given target = 20
, return false
.
检测矩阵中是否存在target,矩阵按每行递增,每列递增规律。
直接用两个for循环遍历数组当然很容易解决,但是可以充分利用给的矩阵的条件。
所以可以从矩阵右上角开始寻找,如果小于target则列-1,如果大于target则行+1。
class Solution: def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ row=len(matrix) if row==0 or len(matrix[0])==0:return False col=len(matrix[0]) r,c=0,col-1 while r=0: num=matrix[r][c] if target==num: return True elif target
转载地址:http://yjrbb.baihongyu.com/