【LeetCode Hot100】搜索二维矩阵 II[特殊字符]二分查找 vs 线性搜索，Java实现，图解+代码

ops/2025/2/26 21:38:23/

💻 [LeetCode Hot100] 搜索二维矩阵 II🔥二分查找 vs 线性搜索，Java实现，图解+代码

✏️本文对应题目链接：搜索二维矩阵 II

📌 题目描述

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

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

示例：

java">输入：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
解释：目标值 5 存在于矩阵中。

🧠 解题思路（图文分解）

❗ 核心难点

如何利用矩阵的特性高效搜索目标值？

方法一：线性搜索（黄金思路）✨

关键步骤：

从右上角开始搜索：
- 如果当前值等于 target，返回 true
- 如果当前值大于 target，向左移动一列
- 如果当前值小于 target，向下移动一行
终止条件：当行或列超出矩阵范围时停止

图解线性搜索

输入矩阵：

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

步骤1：从右上角开始

初始位置：(0,4) → 15 > 5 → 向左移动

步骤2：向左移动

位置：(0,3) → 11 > 5 → 向左移动

步骤3：向左移动

位置：(0,2) → 7 > 5 → 向左移动

步骤4：向左移动

位置：(0,1) → 4 < 5 → 向下移动

步骤5：向下移动

位置：(1,1) → 5 == 5 → 找到目标值

最终结果：

true

🚀 代码实现

java">class Solution {public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return false;}int row = 0, col = matrix[0].length - 1; // 从右上角开始while (row < matrix.length && col >= 0) {if (matrix[row][col] == target) {return true;} else if (matrix[row][col] > target) {col--; // 向左移动} else {row++; // 向下移动}}return false;}
}

💡 复杂度分析

时间复杂度：O(m + n) → 最坏情况下需要遍历一行和一列
空间复杂度：O(1) → 仅用常数空间

方法二：二分查找（优化思路）

关键思路：对每一行进行二分查找，适合列数较大的情况。

java">class Solution {public boolean searchMatrix(int[][] matrix, int target) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return false;}for (int[] row : matrix) {if (binarySearch(row, target)) {return true;}}return false;}private boolean binarySearch(int[] row, int target) {int left = 0, right = row.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (row[mid] == target) {return true;} else if (row[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return false;}
}