LeetCode第240题 编写一个高效的算法来搜索 m x n

来源：LeetCode第240题
难度：中等

编写一个高效的算法来搜索 m * n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
1，每行的元素从左到右升序排列。
2，每列的元素从上到下升序排列。

输入：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

思路分析：
1、二维数组每行每列都是有序的，所以检测方案是可以从左下角出发，也可以从右上角出发判断。原因是每行的元素从左到右升序排列，每列的元素从上到下升序排列。左下角和右上角都可以保证首次判断后可以准确的移动方向，而左上角和右下角不具备此特征。
2、左下角为准，判断比左下角的值大，则往右移动，判断比左下角的值小，则往上移动
3、右上角为准，判断比右上角的值大，则往下移动，判断比右上角的值小，则往左移动

实现代码 ，以Swift为例：

//左下角为准
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        guard !matrix.isEmpty, !matrix[0].isEmpty else {
            return false
        }
        
        let m = matrix.count
        let n = matrix[0].count
        
        var row = m-1
        var col = 0
        
        while col < n && row >= 0 {
            if matrix[row][col] == target {
                return true
            } else if matrix[row][col] < target {
                col += 1 //向右移动
            } else {
                row -= 1 //向上移动
            }
        }
        
        return false
    }

// 示例用法
let matrix: [[Int]] = [
    [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]
]
let target = 5
print(searchMatrix(matrix, target))  // 输出 true

//右上角为准
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
    guard !matrix.isEmpty, !matrix[0].isEmpty else {
        return false
    }
    
    let m = matrix.count
    let n = matrix[0].count
    
    var row = 0
    var col = n - 1
    
    while row < m && col >= 0 {
        if matrix[row][col] == target {
            return true
        } else if matrix[row][col] < target {
            row += 1  // 向下移动
        } else {
            col -= 1  // 向左移动
        }
    }
    
    return false
}

// 示例用法
let matrix: [[Int]] = [
    [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]
]
let target = 5
print(searchMatrix(matrix, target))  // 输出 true