1. 题目描述

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

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

示例 1：
searchgrid2.jpg

  1. 输入：matrix = [[1,4,7,11,15],
  2.                [2,5,8,12,19],
  3.                [3,6,9,16,22],
  4.                [10,13,14,17,24],
  5.                [18,21,23,26,30]
  6.               ],target = 5
  7. 输出：true

示例 2：
searchgrid.jpg

  1. 输入：matrix = [[1,4,7,11,15],
  2.                [2,5,8,12,19],
  3.                [3,6,9,16,22],
  4.                [10,13,14,17,24],
  5.                [18,21,23,26,30]
  6.               ], target = 20
  7. 输出：false

提示：

  • m == matrix.length
  • n == matrix[i].lengt
  • 1 <= n, m <= 30
  • -109 <= matix[i][j] <= 10
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -109 <= target <= 109

    2. 解题思路

    对于这道题目我最先想到的方法就是将数组扁平化成一个一维数组，然后逐个遍历查找目标值，不过试过之后发现超出了时间限制。

还有就是暴力法，直接两层遍历数组，直到遍历完到目标值，这样做复杂度也很高。

那我们可以换个思路，我们初始化一个指针，它指向矩阵左下角的元素（也可以是右上角的元素），将目标值和当前值进行对比：

  • 如果目标值小于当前值，就向上移动
  • 如果目标值大于当前值，就向右移动

重复上述步骤，直到找到目标值。如果没找到就返回false。

那为什么只能选取矩阵左下角或者右上角的值作为初始值呢，这是因为：

  • 选左上角的值，如果目标值大于该值，可以往右或者往下移动，不能确定移动方向；
  • 选右下角的值，如果目标值小于该值，可以往左或者往上移动，不能确定移动方向；

所以我们要选取左下角或者右上角的值，这样就能判断移动的方向。

复杂度分析：

  • 时间复杂度：O(n+m)，在每次迭代时，行或列都会递减/递增一次。由于行只能减少 m 次，而列只能增加 n 次，因此在导致 while 循环终止之前，循环不能运行超过 n+m 次。因为所有其他的工作都是常数，所以总的时间复杂度在矩阵维数之和中是线性的。

  • 空间复杂度：O(1)，因为这种方法只处理几个指针，所以它的内存占用是恒定的。

    3. 代码实现

    （1）暴力求解

    1. /**
    2. * @param {number[][]} matrix
    3. * @param {number} target
    4. * @return {boolean}
    5. */
    6. var searchMatrix = function(matrix, target) {
    7.  if(!matrix.length) return false
    9.   for (let i = 0; i < matrix.length; i++) {
    10.           for (let j = 0; j < matrix[0].length; j++) {
    11.               if (matrix[i][j] == target) {
    12.                   return true;
    13.               }
    14.           }
    15.   }
    16.   return false;
    17. };

    （2）数组扁平化（超时）

    1. /**
    2. * @param {number[][]} matrix
    3. * @param {number} target
    4. * @return {boolean}
    5. */
    6. var searchMatrix = function(matrix, target) {
    7.  if(!matrix.length) return false
    8.   let arr = matrix.flat(1)
    10.   for(let i = 0; i< arr.length; i++){
    11.       if(arr[i] == target){
    12.           return true
    13.       }
    14.   }
    15.   return false
    16. };

    （3）指针

    1. /**
    2. * @param {number[][]} matrix
    3. * @param {number} target
    4. * @return {boolean}
    5. */
    6. var searchMatrix = function(matrix, target) {
    7.  if(!matrix.length) return false
    8.   const m = matrix.length, n = matrix[0].length
    9.   let row = m - 1, col = 0
    11.   while(row >= 0 && col < n){
    12.       if(matrix[row][col] > target){
    13.           row--
    14.       }else if(matrix[row][col] < target){
    15.           col++
    16.       }else{
    17.           return true
    18.       }
    19.   }
    20.   return false;
    21. };

    4. 提交结果

    image.png