2021-01-25 | 240. 搜索二维矩阵 II

傷城~ 2022-10-29 11:28 90阅读 0赞

### 1. 题目描述 ###

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

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

示例 1：![在这里插入图片描述][20210213230105116.jpg]

输入：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：  
![在这里插入图片描述][20210213230002260.jpg]

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

提示：

*  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）暴力求解**

/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */
    var searchMatrix = function(matrix, target) { 
       if(!matrix.length) return false
       
        for (let i = 0; i < matrix.length; i++) { 
                for (let j = 0; j < matrix[0].length; j++) { 
                    if (matrix[i][j] == target) { 
                        return true;
                    }
                }
        }
        return false;
    };

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

/** * @param {number[][]} matrix * @param {number} target * @return {boolean} */
    var searchMatrix = function(matrix, target) { 
       if(!matrix.length) return false
        let arr = matrix.flat(1)
    
        for(let i = 0; i< arr.length; i++){ 
            if(arr[i] == target){ 
                return true
            }
        }
        return false
    };

**（3）指针**

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

### 4. 提交结果 ###

![在这里插入图片描述][20210213225944744.png]

[20210213230105116.jpg]: /images/20221024/11aaae3075c549329f6d5eef545c2bd2.png?
[20210213230002260.jpg]: /images/20221024/b419e8d785494e59b7e0aa7aa680eaa5.png?
[20210213225944744.png]: /images/20221024/c8a021c0a3b442ba9257ba7f5275f30d.png?