思路一：通过遍历主对角线上元素判断查找方向
-
主对角线遍历：
- 遍历主对角线上的每个元素（
matrix[i][i]），其中i的范围是[0, min(m, n) - 1]。 - 如果目标值小于当前主对角线元素，说明目标值可能在当前元素的左上区域（即当前行的左侧或当前列的上方）。
- 如果目标值大于主对角线上的所有元素，则需要在剩余的行和列中继续查找。
- 遍历主对角线上的每个元素（
-
二分查找辅助函数：
binarySearchRow：在给定的行范围[0, colLimit-1]上进行二分查找。binarySearchCol：在给定的列范围[0, rowLimit-1]上进行二分查找。
-
查找策略：
- 每次遍历主对角线元素时，通过二分查找缩小范围，分别查找目标值是否在当前行或当前列中。
#include <vector>
#include <algorithm> // for std::lower_bound
using namespace std;class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size();int n = matrix[0].size();int len = min(m, n); // 主对角线的长度for (int i = 0; i < len; ++i) {// 如果主对角线上的元素等于目标值，直接返回 trueif (matrix[i][i] == target) {return true;}// 如果目标值小于主对角线上的元素，目标可能在当前行的左侧或当前列的上方if (matrix[i][i] > target) {// 在第 i 行的左侧 [0, i-1] 范围内查找if (binarySearchRow(matrix, target, i)) {return true;}// 在第 i 列的上方 [0, i-1] 范围内查找if (binarySearchCol(matrix, target, i)) {return true;}// 如果在当前行和列都没有找到，直接返回 falsereturn false;}}// 如果目标值大于主对角线上的所有元素，则在剩余行和列中查找return false;}private:// 在第 rowIndex 行的 [0, colLimit-1] 范围内进行查找bool binarySearchRow(const vector<vector<int>>& matrix, int target, int rowLimit) {auto it = lower_bound(matrix[rowLimit].begin(), matrix[rowLimit].begin() + rowLimit, target);return it != matrix[rowLimit].begin() + rowLimit && *it == target;}// 在第 colIndex 列的 [0, rowLimit-1] 范围内进行查找bool binarySearchCol(const vector<vector<int>>& matrix, int target, int colLimit) {vector<int> column;for (int i = 0; i < colLimit; ++i) {column.push_back(matrix[i][colLimit]);}auto it = lower_bound(column.begin(), column.end(), target);return it != column.end() && *it == target;}
};- 时间复杂度：
O((min(m, n))²) - 空间复杂度：
O(min(m, n))
思路二：暴力解法
遍历矩阵，查找成功返回true，否则返回false
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size();int n = matrix[0].size();//矩阵为空查找失败if(n == 0){return false;}//目标越界查找失败if(target < matrix[0][0] || target > matrix[m - 1][n - 1]){return false;}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)
思路三：二分查找
由于矩阵内部数字是升序的，在每一行中进行二分查找，查找成功返回true，否则返回false
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {//遍历矩阵中第一列的所有元素for(auto &row: matrix){//在每一行中进行二分查找auto it = lower_bound(row.begin(), row.end(), target);//查找成功返回trueif(it != row.end() && *it == target){return true;}}//查找不成功返回falsereturn false;}
};- 时间复杂度：O(nlogn)，注：二分查找算法的时间复杂度为O(logn)
- 空间复杂度：O(1)
获取迭代器值的四种方法：
- 使用解引用运算符 *
vector<int> vec = {1, 3, 5, 7, 9}; auto it = lower_bound(vec.begin(), vec.end(), 3); int value = *it; // 直接获取值- 获取下标位置（仅适用于连续容器如vector）
vector<int> vec = {1, 3, 5, 7, 9}; auto it = lower_bound(vec.begin(), vec.end(), 3); int index = it - vec.begin(); // 获取下标位置 int value = vec[index]; // 通过下标获取值- 对于pair或结构体类型，使用箭头运算符 ->
vector<pair<int, string>> vec = {{1,"a"}, {3,"b"}, {5,"c"}}; auto it = lower_bound(vec.begin(), vec.end(), make_pair(3, "")); int first = it->first; // 获取pair的first string second = it->second; // 获取pair的second- 使用迭代器的distance函数获取位置
vector<int> vec = {1, 3, 5, 7, 9}; auto it = lower_bound(vec.begin(), vec.end(), 3); int index = distance(vec.begin(), it);
注意：在使用迭代器之前，应该先检查迭代器是否有效，避免解引用end()迭代器。
思路四：Z字形查找
从右上角向左下角，如果当前遍历到的数字大于目标值，就向左移动，如果当前遍历到的数字小于目标值，就向下移动，遍历到目标值返回true，否则返回false
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size();int n = matrix[0].size();//（x,y）为矩阵右上角数字的坐标int x = 0, y = n - 1;//从右上角开始向左下角遍历while(x < m && y >= 0){//查找成功返回trueif(matrix[x][y] == target){return true;}// 如果当前值大于目标值，则向左移动一列// （因为矩阵的每一行从左到右递增）else if(matrix[x][y] > target){--y;}// 如果当前值小于目标值，则向下移动一行// （因为矩阵的每一列从上到下递增）else{++x;}}// 如果遍历结束仍未找到目标值，返回 falsereturn false;}
};- 时间复杂度：O(m+n)
- 空间复杂度：O(1)
同时也可以从左下角向右上角进行查找，只需要基于上述代码进行少量修改：
int x = m - 1, y = 0; //从左下角开始向右上角遍历 while(x >= 0 && y < n){//查找成功返回trueif(matrix[x][y] == target){return true;}// 如果当前值大于目标值，则向上移动一列// （因为矩阵的每一行从上到下递增）else if(matrix[x][y] > target){--x;}// 如果当前值小于目标值，则向右移动一行// （因为矩阵的每一列左到右递增）else{++y;} }