公司建网站的详细步骤,简洁大方的网站首页,企业所得税计算方式,网站开发 文学LeetCode 热题 100 | 74. 搜索二维矩阵
大家好#xff0c;今天我们来解决一道经典的算法题——搜索二维矩阵。这道题在 LeetCode 上被标记为中等难度#xff0c;要求我们在一个满足特定条件的二维矩阵中查找一个目标值。如果目标值在矩阵中#xff0c;返回 true#xff1b…LeetCode 热题 100 | 74. 搜索二维矩阵
大家好今天我们来解决一道经典的算法题——搜索二维矩阵。这道题在 LeetCode 上被标记为中等难度要求我们在一个满足特定条件的二维矩阵中查找一个目标值。如果目标值在矩阵中返回 true否则返回 false。下面我将详细讲解解题思路并附上 Python 代码实现。 问题描述
给定一个满足以下两个条件的 m x n 整数矩阵
每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
你需要判断一个整数 target 是否在矩阵中。
示例 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解题思路
核心思想 二分查找 由于矩阵的每一行都是有序的并且每行的第一个元素大于前一行的最后一个元素整个矩阵可以看作是一个一维有序数组。因此可以使用二分查找来高效地查找目标值。 映射二维索引到一维索引 将二维矩阵的索引映射到一维数组的索引方便进行二分查找。 Python代码实现
def searchMatrix(matrix, target)::type matrix: List[List[int]]:type target: int:rtype: boolif not matrix or not matrix[0]:return Falsem, n len(matrix), len(matrix[0]) # 获取矩阵的行数和列数left, right 0, m * n - 1 # 初始化二分查找的左右边界while left right:mid (left right) // 2 # 计算中间索引mid_value matrix[mid // n][mid % n] # 将一维索引映射到二维索引if mid_value target:return True # 找到目标值返回 Trueelif mid_value target:left mid 1 # 目标值在右侧移动左边界else:right mid - 1 # 目标值在左侧移动右边界return False # 未找到目标值返回 False# 测试示例
print(searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3)) # 输出: True
print(searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13)) # 输出: False代码解析 初始化边界 left 初始化为 0right 初始化为矩阵的最后一个元素的索引 m * n - 1。 二分查找 在 left right 的范围内计算中间索引 mid。将一维索引 mid 映射到二维索引 matrix[mid // n][mid % n]。如果 mid_value 等于目标值直接返回 True。如果 mid_value 小于目标值说明目标值在右侧将 left 移动到 mid 1。如果 mid_value 大于目标值说明目标值在左侧将 right 移动到 mid - 1。 返回结果 如果未找到目标值循环结束后返回 False。 复杂度分析
时间复杂度O(log(m * n))其中 m 是矩阵的行数n 是矩阵的列数。二分查找的时间复杂度为 O(log(m * n))。空间复杂度O(1)只使用了常数个额外空间。 示例运行
示例 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总结
通过将二维矩阵的索引映射到一维索引我们可以使用二分查找高效地查找目标值。这种方法不仅简洁而且效率非常高适合处理类似的问题。希望这篇题解对大家有所帮助如果有任何问题欢迎在评论区留言讨论
关注我获取更多算法题解和编程技巧
