跳转至

LC240 - 搜索二维矩阵II

SearchA2DMatrixII.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
package Matrix

// 时间复杂度: O(n + m), 空间复杂度: O(1)
func searchMatrix(matrix [][]int, target int) bool {
    n, m := len(matrix), len(matrix[0])
    if target < matrix[0][0] || target > matrix[n-1][m-1] {
        return false
    }
    curX, curY := n-1, 0
    for curX >= 0 && curX < n && curY >= 0 && curY < m {
        if matrix[curX][curY] < target {
            curY++
        } else if matrix[curX][curY] > target {
            curX--
        } else {
            return true
        }
    }
    return false
}

取矩阵左下角元素为起始参考点cur，cur > target则可以删除cur所在行，cur < target则可以删除cur所在列。