240-搜索二维矩阵II.md

题目描述

搜索二维矩阵 II

题目简述

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

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

分类

中等 数组 待优化 二分

思路

思路1

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
  // 列
  for (let ci = matrix[0].length - 1; ci >= 0 ; ci--) {
    if (target < matrix[0][ci]) continue
    if (target > matrix[matrix.length - 1][ci]) break
    // 行
    for (let ri = matrix.length - 1; ri >= 0; ri --) {
      if (target > matrix[ri][ci]) continue
      if (target === matrix[ri][ci]) return true
    }
  }
  return false
};

• 问题分析
  • 对于每列，从最后一列往前推，如果target小于该列的第一个值，由于每列的递增的所以target不可能存在于该列中；如果target大于该列最后一个值，由于所有列的最后一个值也是递增的，所以target也不可能存在于往前的列中。
  • 如果不属于上述俩种情况，target可能存在于该列中，从该列的最大值开始推，如果相等，则直接返回true，如果target大于过程中的某值则直接跳过。
  • 后续用二分进行优化。