引言
搜索二维矩阵 II
- 🎈 题目链接：
- 🎈 做题状态：
我的解题
有三种方法，只想到了前两种，第三种没有想到。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
// 1. 暴力搜索
// 2. 二分法查找
// 3. 贪心优化
for (const auto& row : matrix)
{
for (const auto& elem : row)
{
if (elem == target)
{
return true;
}
}
}
return false;
}
};
二分查找：
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
// 1. 暴力搜索
// 2. 二分法查找
// 3. 贪心优化
for (const auto& row : matrix)
{
// 每一行采用二分查找
bool res = binary_search(row.begin(), row.end(), target);
if (res) return true;
}
return false;
}
};
贪心求解
解题思路详解
这种方法的巧妙之处在于充分利用了矩阵的两个排序特性：
- 行有序：每一行从左到右升序排列
- 列有序：每一列从上到下升序排列
搜索策略（以从右上角开始为例）
起始点选择：从矩阵的右上角（即第一行最后一列）开始搜索
- 这个位置的元素是该行的最大值，该列的最小值
- 这种特殊性质为我们提供了明确的移动方向
比较与移动规则：
- 当前元素 == 目标值：直接返回找到
- 当前元素 > 目标值：说明目标值不可能在当前列（因为当前列下面的元素都更大），所以向左移动一列
- 当前元素 < 目标值：说明目标值不可能在当前行（因为当前行左边的元素都更小），所以向下移动一行
终止条件：
- 找到目标值返回true
- 行或列越界时（row >= m 或 col < 0）返回false
为什么这种方法有效？
- 不会错过目标值：每次移动都排除了不可能包含目标值的行或列
- 路径最优：每次比较都能最大限度地缩小搜索范围
- 效率高：最多只需m+n-1次比较（从右上角到左下角的路径）
完整代码实现
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
// 处理空矩阵的特殊情况
if (matrix.empty() || matrix[0].empty()) {
return false;
}
// 获取矩阵的行数(m)和列数(n)
int m = matrix.size(); // 行数
int n = matrix[0].size(); // 列数
// 初始化搜索起点为右上角(第一行最后一列)
int row = 0; // 起始行
int col = n - 1; // 起始列
// 在矩阵范围内进行搜索
while (row < m && col >= 0) {
// 获取当前元素值
int current = matrix[row][col];
if (current == target) {
// 找到目标值，直接返回true
return true;
} else if (current > target) {
// 当前值太大，目标值可能在当前列的左侧
col--; // 向左移动一列
} else {
// 当前值太小，目标值可能在当前行的下方
row++; // 向下移动一行
}
}
// 搜索结束仍未找到，返回false
return false;
}
};
复杂度分析
- 时间复杂度：O(m + n)
- 最坏情况下需要从右上角移动到左下角
- 每次循环排除一行或一列
- 空间复杂度：O(1)
- 只使用了常数个额外空间
示例演示
以查找目标值5为例：
矩阵：
[
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10,13,14,17]
]
搜索路径：
1. 从11开始 (11 > 5) → 左移
2. 到7 (7 > 5) → 左移
3. 到4 (4 < 5) → 下移
4. 到5 (5 == 5) → 找到
这种贪心搜索法是解决此类二维矩阵搜索问题的最优方法之一，既高效又直观。