详情

    暴力破解，时间复杂度 O(mn),空间复杂度 O(1)

    1. func searchMatrix(matrix [][]int, target int) bool {
    2.     for _, row := range matrix {
    3.         for _, v :=  range row {
    4.             if v == target {
    5.                 return true
    6.             }
    7.         }
    8.     }
    9.     return false
    10. }

    增加二分法，时间复杂度 O(mlogn)，空间复杂度 O(1)

    func searchMatrix(matrix [][]int, target int) bool {
    for _, row := range matrix {
        i := sort.SearchInts(row, target)
        if i < len(row) && row[i] == target {
            return true
        }
    }
    return false
}

    Z 字查找，时间复杂度 O(m+n)，空间复杂度 O(1)
    主要利用了矩阵本身的特性：

    • 每行的元素从左到右升序排列。
    • 每列的元素从上到下升序排列。
      func searchMatrix(matrix [][]int, target int) bool {
  m, n := len(matrix), len(matrix[0])
  x, y := 0, n-1
  for x < m && y >= 0 {
      if matrix[x][y] == target {
          return true
      }
      if matrix[x][y] > target {
          y--
      } else {
          x++
      }
  }
  return false
}