LeetCode 74. Search a 2D Matrix 题解

LeetCode 74. Search a 2D Matrix 题解

题目描述

编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

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

解题思路

方法：二分查找

思路：

• 由于矩阵的每行都是升序排列，且每行的第一个整数大于前一行的最后一个整数，所以整个矩阵可以看作是一个一维的有序数组。
• 我们可以使用二分查找来快速定位目标值。
• 具体步骤：
  1. 计算矩阵的总元素个数total = m * n。
  2. 初始化左指针left为 0，右指针right为total - 1。
  3. 当left <= right时，计算中间位置mid。
  4. 将mid转换为二维坐标(row, col)，其中row = mid // n，col = mid % n。
  5. 比较matrix[row][col]与目标值的大小：
     • 如果相等，返回true。
     • 如果小于目标值，将left设为mid + 1。
     • 如果大于目标值，将right设为mid - 1。
  6. 如果循环结束仍未找到目标值，返回false。

复杂度分析：

• 时间复杂度：O(log(m * n))，其中 m 和 n 分别是矩阵的行数和列数。每次查找都会将查找区间减半。
• 空间复杂度：O(1)，只需要常数级的额外空间。

代码实现

方法：二分查找

class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: # 处理边界情况 if not matrix or not matrix[0]: return False # 获取矩阵的行数和列数 m = len(matrix) n = len(matrix[0]) # 计算总元素个数 total = m * n # 初始化左指针和右指针 left = 0 right = total - 1 # 当左指针小于等于右指针时，继续查找 while left <= right: # 计算中间位置 mid = left + (right - left) // 2 # 将中间位置转换为二维坐标 row = mid // n col = mid % n # 获取中间元素 mid_val = matrix[row][col] # 如果找到目标值，返回 true if mid_val == target: return True # 如果中间值小于目标值，将左指针移到中间位置的右边 elif mid_val < target: left = mid + 1 # 如果中间值大于目标值，将右指针移到中间位置的左边 else: right = mid - 1 # 如果没有找到目标值，返回 false return 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

总结

本题是二分查找的经典变体问题，主要考察对二分查找算法的理解和应用。通过将二维矩阵看作一维有序数组，我们可以使用二分查找来高效地定位目标值。

二分查找的核心思想是：使用两个指针分别指向查找区间的两端，计算中间位置，比较中间元素与目标值的大小，根据比较结果缩小查找区间，直到找到目标值或确定目标值不存在。

这种方法的时间复杂度为 O(log(m * n))，适用于大规模二维矩阵的查找。掌握二分查找的原理，对于理解搜索算法和算法设计思想非常重要。