74. 搜索二维矩阵

74. 搜索二维矩阵 #

链接 #

74. 搜索二维矩阵

题目 #

给你一个满足下述两条属性的 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

解答 #

  1. 初始化两个指针，top 和 bottom，分别指向矩阵的第一行和最后一行。
  2. 当 top 小于等于 bottom 时，进行以下操作：
    • 找到 top 和 bottom 指向的行的中间行，记为 mid。
    • 在中间行使用二分查找来确定目标值是否在这一行。如果找到目标值，返回 True。
    • 如果目标值小于中间行的第一个元素，则更新 bottom 为 mid - 1。
    • 如果目标值大于中间行的最后一个元素，则更新 top 为 mid + 1。
  3. 如果在循环结束后仍未找到目标值，则返回 False。 这种方法的时间复杂度为 $O(\log m + \log n)$，其中 $m$ 是矩阵的行数，$n$ 是矩阵的列数。 接下来，我将用 Python 实现这个算法。
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        top, bottom = 0, len(matrix) - 1
        while top <= bottom:
            mid = (top + bottom) // 2
            row = matrix[mid]
            # Perform binary search on the row
            left, right = 0, len(row) - 1
            while left <= right:
                pivot = (left + right) // 2
                if row[pivot] == target:
                    return True
                if row[pivot] < target:
                    left = pivot + 1
                else:
                    right = pivot - 1
            # Adjust top and bottom for next iteration
            if row[0] > target:
                bottom = mid - 1
            elif row[-1] < target:
                top = mid + 1
            else:
                # This condition means the target is not in this row,
                # but could be in the previous or next row.
                return False
        return False
Edit Edit this page