【LeetCodeHOT100】240. 搜索二维矩阵 II——Java多解法详解

一、题目描述题目链接240. 搜索二维矩阵 II难度中等题目描述编写一个高效的算法来搜索 m x n 矩阵matrix中的一个目标值target。该矩阵具有以下特性每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例 1text输入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示例 2text输入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.lengthn matrix[i].length1 n, m 300-10⁹ matrix[i][j] 10⁹每行的所有元素从左到右升序排列每列的所有元素从上到下升序排列-10⁹ target 10⁹二、思路分析这道题要求在一个行有序且列有序的二维矩阵中高效查找目标值。矩阵的排序特性如下单行内部严格从左到右递增单列内部严格从上到下递增跨行不一定整体有序比如最后一行开头可能比上一行末尾小正因为这个特性不能直接把矩阵展平成一维数组做二分查找需要巧妙利用矩阵的有序规律。核心解题突破口仔细观察矩阵的四个角落位置特点能否作为起点左上角行内最小值、列内最小值❌ 无法排除行/列右下角行内最大值、列内最大值❌ 无法排除行/列右上角行内最大值、列内最小值✅ 可排除行/列左下角行内最小值、列内最大值✅ 可排除行/列以右上角为例右上角是当前行的最大值、当前列的最小值。如果当前值大于 target说明这一整列都不可能存在 target因为该列从上到下递增当前值是最小的可以直接排除这一列向左移动如果当前值小于 target说明这一整行都不可能存在 target因为该行从左到右递增当前值是最大的可以直接排除这一行向下移动。这样每一步都能排除一行或一列将时间复杂度从 O(m×n) 优化到 O(mn)。三、解法一暴力法不推荐思路最简单的思路是双层遍历逐个比对每个元素。代码实现javaclass Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix null || matrix.length 0 || matrix[0].length 0) { return false; } int m matrix.length; int n matrix[0].length; for (int i 0; i m; i) { for (int j 0; j n; j) { if (matrix[i][j] target) { return true; } } } return false; } }复杂度分析时间复杂度O(m×n)需要遍历所有元素空间复杂度O(1)⚠️ 暴力法虽然能通过小数据但题目明确要求“高效的算法”面试中直接写暴力法会被判定不合格。四、解法二逐行二分查找思路由于矩阵每一行都是升序排列的可以对每一行分别进行二分查找。代码实现javaclass Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix null || matrix.length 0 || matrix[0].length 0) { return false; } int m matrix.length; int n matrix[0].length; for (int i 0; i m; i) { int left 0, right n - 1; // 当前行最小值大于 target直接跳过 if (matrix[i][left] target) { continue; } // 当前行最大值小于 target直接跳过 if (matrix[i][right] target) { continue; } // 二分查找 while (left right) { int mid left (right - left) / 2; if (matrix[i][mid] target) { return true; } else if (matrix[i][mid] target) { left mid 1; } else { right mid - 1; } } } return false; } }复杂度分析时间复杂度O(m × log n)每行二分查找 O(log n)共 m 行空间复杂度O(1)五、解法三Z字形查找推荐思路这是本题的最优解法。从右上角或左下角出发利用矩阵的行列排序特性每一步排除一整行或一整列将查找范围逐步缩小。查找规则以右上角为起点从矩阵右上角matrix[0][n-1]开始如果当前值 target→ 找到目标返回true如果当前值 target→ target 不可能在当前列向左移动一列排除当前列如果当前值 target→ target 不可能在当前行向下移动一行排除当前行如果越界仍未找到 → 返回false图解示例以示例矩阵为例查找 target 5text初始位置右上角 matrix[0][4] 15 15 5 → 排除第4列整列都比5大向左移动 → matrix[0][3] 11 11 5 → 排除第3列向左移动 → matrix[0][2] 7 7 5 → 排除第2列向左移动 → matrix[0][1] 4 4 5 → 排除第0行整行都比5小向下移动 → matrix[1][1] 5 5 5 → 找到返回 true整个过程共移动了 4 步没有遍历整个矩阵。代码实现javaclass Solution { public boolean searchMatrix(int[][] matrix, int target) { // 边界条件判断 if (matrix null || matrix.length 0 || matrix[0].length 0) { return false; } int m matrix.length; int n matrix[0].length; // 从右上角开始搜索 int i 0, j n - 1; while (i m j 0) { if (matrix[i][j] target) { return true; } else if (matrix[i][j] target) { // 当前值大于 target向左移动排除当前列 j--; } else { // 当前值小于 target向下移动排除当前行 i; } } return false; } }以左下角为起点的等价写法javaclass Solution { public boolean searchMatrix(int[][] matrix, int target) { if (matrix null || matrix.length 0 || matrix[0].length 0) { return false; } int m matrix.length; int n matrix[0].length; // 从左下角开始搜索 int i m - 1, j 0; while (i 0 j n) { if (matrix[i][j] target) { return true; } else if (matrix[i][j] target) { // 当前值大于 target向上移动 i--; } else { // 当前值小于 target向右移动 j; } } return false; } }复杂度分析时间复杂度O(m n)。最坏情况下从右上角走到左下角最多遍历 m n 个元素。空间复杂度O(1)只用了常数个变量。六、解法对比总结解法核心思路时间复杂度空间复杂度面试推荐度暴力法双层遍历O(m×n)O(1)⭐不推荐逐行二分每行二分查找O(m×log n)O(1)⭐⭐⭐Z字形查找从右上角出发排除行/列O(mn)O(1)⭐⭐⭐⭐⭐结论Z字形查找是最优解法充分利用了矩阵的行列排序特性是面试中的首选写法。七、面试高频追问Q1为什么不能从左上角或右下角开始左上角是全局最小值右下角是全局最大值。从这两个点出发如果当前值小于 target你无法确定是向下还是向右移动因为两个方向都是递增的。而右上角和左下角恰好保证了只有一个方向是递增、一个方向是递减因此每次比较都能唯一确定排除一行或一列。Q2Z字形查找的时间复杂度为什么是 O(mn)因为每一步要么向右列减1、要么向下行加1最多只能移动 m n 步就会越界。Q3如果矩阵的行数远大于列数能否进一步优化可以结合两种思路当 m n 时可以先在列方向做二分查找找到目标值可能在的行范围再对每一行进行二分查找但这会使代码复杂度增加。一般情况下 Z字形查找已经足够高效。八、相关题目推荐74. 搜索二维矩阵 —— 矩阵整体有序的版本可以直接用二分查找378. 有序矩阵中第 K 小的元素 —— 利用行列排序特性查找第 K 小元素九、参考资料官方题目链接240. 搜索二维矩阵 II - 力扣LeetCode官方题解链接240. 搜索二维矩阵 II - 官方题解