搜索二维矩阵-ii

题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target. 该矩阵具有以下特性:

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

提示:

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10⁹ <= matrix[i][j] <= 10⁹
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -10⁹ <= target <= 10⁹

示例

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

题解

核心就是从左下角开始, 往右上角移动, 直到找到或者找不到.

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  let i = matrix.length - 1
  let j = 0

  while (i >= 0 && j < matrix[0].length) {
    if (matrix[i][j] > target) {
      i--
    } else if (matrix[i][j] < target) {
      j++
    } else {
      return true
    }
  }
  return false
}