LeetCode/二维矩阵搜索
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
1. 暴力求解
两重循环，时间复杂度O(m*n）
两重循环
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
for (const auto& row: matrix) {
for (int element: row) {
if (element == target) {
return true;
}
}
}
return false;
}
};
2. Z字形双指针
由于二维数组在行列上分别满足升序，可以用两个指针分别找出其在行与列上的位置
行从前往后遍历，列从后往前遍历，之所以不能同时一个方向，是与target比较时，无法决定先移动哪个指针
时间复杂度为O(m+n）
Z字形双指针
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int x = 0, y = n - 1;
while (x < m && y >= 0) {
if (matrix[x][y] == target) {
return true;
}
if (matrix[x][y] > target) {
--y;
}
else {
++x;
}
}
return false;
}
};
3. 回溯法（深度优先）
递归向右和向下，对于遍历过的路径做标记防止重复
时间复杂度应该为O(m*n),但不知道为什么实际执行时性能比方法二还好
回溯法
class Solution {
public:
bool flag=false;
bool searchMatrix(vector>& matrix, int target) {
search(matrix,target,0,0);
return flag;
}
void search(vector>& matrix,int target,int i,int j){
if(flag==true||matrix[i][j]==-2) return; //剪去其他遍历分支
if(matrix[i][j]==target){ flag=true; return;}//满足条件跳出遍历
if(matrix[i][j]