240. 搜索二维矩阵 II

题目

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

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

题解

矩阵特性

根据矩阵特性

初始化指针指向矩阵左下角

• 目标大于指针值，指针向右
• 目标小于指针值，指针向上
• 等于返回 true
• 越界返回 false

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
  let rows = matrix.length;
  let cols = matrix[0].length;

  let r = rows - 1,
    c = 0;

  while (r < rows && r >= 0 && c >= 0 && c < cols) {
    let t = matrix[r][c];
    if (t == target) return true;
    else if (t < target) c++;
    else r--;
  }
  return false;
};

时间复杂度：O(m+n) m n 分别为行数和列数 空间复杂度：O(1)