现在流行的网站开发工具,网站首页设计思路,免费发帖论坛大全,精品课程网站源码目录 题目描述解法方法一#xff1a;二分查找方法二#xff1a;从左下角或右上角搜索 运行结果方法一方法二 题目描述
给你一个满足下述两条属性的 m x n 整数矩阵#xff1a;
每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
给… 目录 题目描述解法方法一二分查找方法二从左下角或右上角搜索 运行结果方法一方法二 题目描述
给你一个满足下述两条属性的 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.lengthn matrix[i].length1 m, n 100-104 matrix[i][j], target 104 解法
方法一二分查找
我们将二维矩阵逻辑展开然后二分查找即可。
时间复杂度 O(log(m×n))。其中 m 和 n 分别是矩阵的行数和列数。空间复杂度 O(1)。
class Solution(object):def searchMatrix(self, matrix, target)::type matrix: List[List[int]]:type target: int:rtype: boolm, n len(matrix), len(matrix[0])left, right 0, m * n - 1while left right:mid (left right) 1x, y divmod(mid, n)if matrix[x][y] target:right midelse:left mid 1return matrix[left // n][left % n] target方法二从左下角或右上角搜索
这里我们以左下角作为起始搜索点往右上方向开始搜索比较当前元素 matrix[i][j] 与 target 的大小关系
若 matrix[i][j]target说明找到了目标值直接返回 true。若 matrix[i][j]target说明这一行从当前位置开始往右的所有元素均大于 target应该让 i 指针往上移动即 ii−1。若 matrix[i][j]target说明这一列从当前位置开始往上的所有元素均小于 target应该让 j 指针往右移动即 jj1。
若搜索结束依然找不到 target返回 false。
时间复杂度 O(mn)。其中 m 和 n 分别是矩阵的行数和列数。空间复杂度 O(1)。
class Solution(object):def searchMatrix(self, matrix, target)::type matrix: List[List[int]]:type target: int:rtype: boolm, n len(matrix), len(matrix[0])i, j m - 1, 0while i 0 and j n:if matrix[i][j] target:return Trueif matrix[i][j] target:i - 1else:j 1return False运行结果
方法一 方法二
