168 - 240 搜索二维矩阵2 - 001

题目

编写一个高效的算法来搜索 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。

给定 target = 20，返回 false。

解答

https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-2/

从左下角开始，一点点向上找。如果遇到大的，就像上一行；遇到小的就向右一行。

class Solution:
    def searchMatrix(self, matrix, target):
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        height, width = len(matrix), len(matrix[0])
        row, col = height-1, 0
        while row >= 0 and col < width:
            if matrix[row][col] > target:
                row -= 1
            elif matrix[row][col] < target:
                col += 1
            else:
                return True
        return False

Runtime: 36 ms, faster than 82.14% of Python3 online submissions for Search a 2D Matrix II.

Memory Usage: 17.4 MB, less than 92.59% of Python3 online submissions for Search a 2D Matrix II.

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }
    height := len(matrix)
    width := len(matrix[0])
    row := height - 1
    col := 0
    for row >= 0 && col < width {
        if matrix[row][col] > target {
            row--
        } else if matrix[row][col] < target {
            col++
        } else {
            return true
        }
    }
    return false
}

Runtime: 24 ms, faster than 89.76% of Go online submissions for Search a 2D Matrix II.

Memory Usage: 6.2 MB, less than 100.00% of Go online submissions for Search a 2D Matrix II.

var searchMatrix = function(matrix, target) {
  if (matrix.length === 0 || matrix[0].length === 0) {
    return false
  }
  let height = matrix.length
  width = matrix[0].length
  row = height - 1
  col = 0
  while (row >= 0 && col < width) {
    if (matrix[row][col] > target) {
      row--
    } else if (matrix[row][col] < target) {
      col++
    } else {
      return true
    }
  }
  return false
};

Runtime: 80 ms, faster than 79.61% of JavaScript online submissions for Search a 2D Matrix II. Memory Usage: 37.5 MB, less than 33.33% of JavaScript online submissions for Search a 2D Matrix II.