在二维矩阵中高效搜索目标值的方法

问题描述

在一个 m x n 的矩阵 matrix 中搜索一个目标值 target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

例如：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出：true

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 输出：false

解决思路

我们可以利用矩阵的特性：每行的元素从左到右升序排列，每列的元素从上到下升序排列。这使得我们可以使用一种从右上角开始的搜索策略。

详细步骤

1. 从矩阵的右上角开始（即第0行，第n-1列）。
2. 比较当前元素与目标值：
   • 如果当前元素等于目标值，返回 true。
   • 如果当前元素小于目标值，向下移动一行（即增加行索引）。
   • 如果当前元素大于目标值，向左移动一列（即减少列索引）。
3. 重复上述步骤，直到找到目标值或搜索范围超出矩阵边界。

这种方法的时间复杂度是 O(m + n)，其中 m 是矩阵的行数，n 是矩阵的列数。

代码实现

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        
        m, n = 0, len(matrix[0]) - 1
        
        while m < len(matrix) and n >= 0:
            if matrix[m][n] == target:
                return True
            elif matrix[m][n] < target:
                m += 1
            else:
                n -= 1
        
        return False

示例

对于输入 matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5，输出应为 true。

对于输入 matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20，输出应为 false。

这种方法利用了矩阵的排序特性，使得搜索过程高效且简单。