leetcode 240. Search a 2D Matrix II | 240. 搜索二维矩阵 II（Java）

缺乏、安全感 2022-10-09 06:28 155阅读 0赞

## 题目 ##

[https://leetcode.com/problems/search-a-2d-matrix-ii/][https_leetcode.com_problems_search-a-2d-matrix-ii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

### 方法1 ###

思路类似于 [leetcode 200. Number of Islands | 200. 岛屿数量（Java）][leetcode 200. Number of Islands _ 200. _Java] 的“感染”过程，从左上角开始找，递归其右边和下边的格子，同时为了避免重复路线，做了一些优化。trace 用来记录已经走过的路线。

复杂度分析：这种不走重复路线的递归方式，时间复杂度应该是O(m\*n)吧，不是很确定。

class Solution { 
        public boolean searchMatrix(int[][] matrix, int target) { 
            int M = matrix.length;
            int N = matrix[0].length;
            boolean[][] trace = new boolean[M][N]; // 避免重复路线
            return process(matrix, trace, 0, 0, target);
        }
    
        public boolean process(int[][] matrix, boolean[][] trace, int m, int n, int t) { 
            if (m == matrix.length || n == matrix[0].length || matrix[m][n] > t) return false;
            if (matrix[m][n] == t) return true;
            trace[m][n] = true;
            if (m + 1 < matrix.length && !trace[m + 1][n] && process(matrix, trace, m + 1, n, t)) return true;
            else return n + 1 < matrix[0].length && !trace[m][n + 1] && process(matrix, trace, m, n + 1, t);
        }
    }

### 方法2：完美利用矩阵的性质进行查找（最优解） ###

参考：[官方题解][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

从左下角开始，执行以下操作：如果当前值大于目标值，则向上移动；如果当前值小于目标值，则向右移动。

这样做永远不会跳过正确的答案，因为每一行都是升序排列，所以当前值右侧的每个值都更大。 每一列都是升序排列，所以当前值上方的每个值都更小，这决定了**在每一个位置上，下一步的路线是唯一的**。即，**如果当前值已经大于目标值，只能向上走，而入如果当前值小于目标值，只能向右走**。因此，这种搜索方式将始终在矩阵中找到目标（如果存在）。

关于“如何选出发点”的补充：

*  选左上角，往右走和往下走都增大，不能选
 *  选右下角，往上走和往左走都减小，不能选
 *  选左下角，往右走增大，往上走减小，可选
 *  选右上角，往下走增大，往左走减小，可选

class Solution { 
        public boolean searchMatrix(int[][] matrix, int target) { 
            int i = matrix.length - 1;
            int j = 0;
            while (i >= 0 && j < matrix[0].length) { 
                if (matrix[i][j] == target) return true;
                else if (matrix[i][j] > target) i--;
                else j++;
            }
            return false;
        }
    }

### 方法3：暴力遍历 ###

依次比较每个元素。时间复杂度O(m\*n)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

[https_leetcode.com_problems_search-a-2d-matrix-ii]: https://leetcode.com/problems/search-a-2d-matrix-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/92aa04746d624fd690e92355a47d8dcb.png
[leetcode 200. Number of Islands _ 200. _Java]: https://hanquan.blog.csdn.net/article/details/117652280
[Link 1]: https://leetcode-cn.com/problems/search-a-2d-matrix-ii/solution/sou-suo-er-wei-ju-zhen-ii-by-leetcode-2/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/f3c70dfd5e38429a953a1fab530f22ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/c3c7552747804f40aa59a421ffbff28d.png