[LeetCode240. 搜索二维矩阵 II]｜刷题打卡

题目描述

示例 1：

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

示例 2：

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

思路分析

AC代码

每行二分

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  let y = 0
  while (y < matrix.length) {
    let min = 0, max = matrix[0].length - 1
    while (min <= max) {
      let mid = parseInt((min + max) / 2)
      if (matrix[y][mid] === target) {
        return true
      }
      else if (matrix[y][mid] > target) {
        max = mid - 1
      }
      else {
        min = mid + 1
      }
    }
    y++
  }
  return false
};

裁剪法

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

总结

从这一题可以看出，算法在很多地方都跟数学扯上了关系