搜索二维矩阵 II-240

[sl1673495]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

参考：https://zhuanlan.zhihu.com/p/144219651

由题可得，当某一个单元格的值大于目标值的时候，那么目标值一定在这个单元格上方的行里。

如果单元格的值小于目标值的时候，那么目标值一定在这个单元格右边的列里。

根据这一特性，从最左下角那一格开始，设立行指针row = y - 1，设立列指针 column = 0，然后不断根据上面描述特征移动这两个指针，直到找到目标值位置。如果超出边界还没有找到目标值，那么就返回 false。

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
let searchMatrix = function (matrix, target) {
  let y = matrix.length
  if (!y) return false
  let x = matrix[0].length

  let row = y - 1
  let column = 0
  while (row >= 0 && column < x) {
    let val = matrix[row][column]
    if (val > target) {
      row--
    } else if (val < target) {
      column++
    } else if (val === target) {
      return true
    }
  }
  return false
}

[cwjbjy]

绝了，以左下角为起点