设计方案的步骤_家装设计师用什么软件画图_网络推广的渠道_广告设计网站

题目描述：

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

 

示例 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

 

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

 

我的作答：

每行每列搜索，因为矩阵是有序的；

class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:if not matrix: return Falsem = len(matrix)n = len(matrix[0])i, j = 0, 0while i<m and target>matrix[i][n-1]: #比每行的最后一个数大就跳过，+1i += 1if i>=m: return False #如果每行都比target小就falsewhile j<n and target>matrix[i][j]: #该行的列搜索j += 1if j>=n: return False #如果该行没有就falseif target!=matrix[i][j]: #跳出循环此时matrix[i][j]应该>=targetreturn Falseelse: return True

 

时间复杂度O(m+n)，空间复杂度O(1)

 

参考：

二分法O（logmn）

class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:m, n = len(matrix), len(matrix[0])left, right = -1, m * nwhile left + 1 < right:mid = (left + right) // 2x = matrix[mid // n][mid % n]if x == target:return Trueif x < target:left = midelse:right = midreturn False