中等

问题描述

给定 M×N 矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。

示例:

现有矩阵 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。

Z 字形查找

因为矩阵是每一行、每一列都按升序排列的，所以可以从左下角开始搜索:

• 当 $matrix[i][j] > target$ 时指针上移
• 当 $matrix[i][j] < target$ 时指针右移
• 当指针超出边界，说明矩阵中没有这个值，返回 $false$

这样就能减少大部分无效的搜索。

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  if (matrix.length === 0) return false
  let col = 0
  let row = matrix.length - 1
  const length = matrix[0].length
  while (col < length && row > -1) {
    const item = matrix[row][col]
    if (item === target) {
      return true
    } else if (item > target) {
      row--
    } else {
      col++
    }
  }
  return false
}

• 时间复杂度：$O(n + m)$
• 空间复杂度：$O(n)$