LeetCode/二维矩阵搜索(Leetcode / 2D matrix search)-其他

LeetCode/二维矩阵搜索(Leetcode / 2D matrix search)

1. 暴力求解

``````class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for (const auto& row: matrix) {
for (int element: row) {
if (element == target) {
return true;
}
}
}
return false;
}
};
``````

2. Z字形双指针

``````class Solution {
public:
bool searchMatrix(vector<vector<int>>& 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. 回溯法（深度优先）

``````class Solution {
public:
bool flag=false;
bool searchMatrix(vector<vector<int>>& matrix, int target) {
search(matrix,target,0,0);
return flag;
}

void search(vector<vector<int>>& 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]<target) {
matrix[i][j]=-2;//做标记
if(i<matrix.size()-1)
search(matrix,target,i+1,j);//向下递归
if(j<matrix[0].size()-1)
search(matrix,target,i,j+1);//向右递归
}
else matrix[i][j]=-2;//做标记
}
};
``````
————————

Write an efficient algorithm to search for a target value target in the # m # x # n # matrix. The matrix has the following characteristics:

The elements of each row are arranged in ascending order from left to right.
The elements of each column are arranged in ascending order from top to bottom.

1. Violence resolution

Double cycle, time complexity O (m * n)

``````class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for (const auto& row: matrix) {
for (int element: row) {
if (element == target) {
return true;
}
}
}
return false;
}
};
``````

2. Zigzag double pointer

Since the two-dimensional array is in ascending order on the row and column respectively, two pointers can be used to find its position on the row and column respectively
Rows are traversed from front to back, and columns are traversed from back to front. The reason why we can’t move in one direction at the same time is that we can’t decide which pointer to move first when comparing with target
The time complexity is O (M + n)

``````class Solution {
public:
bool searchMatrix(vector<vector<int>>& 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. Backtracking method (depth first)

Recursion to the right and down, and mark the traversed path to prevent repetition
The time complexity should be o (m * n), but I don’t know why the actual performance is better than that of method 2

``````class Solution {
public:
bool flag=false;
bool searchMatrix(vector<vector<int>>& matrix, int target) {
search(matrix,target,0,0);
return flag;
}

void search(vector<vector<int>>& 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]<target) {
matrix[i][j]=-2;//做标记
if(i<matrix.size()-1)
search(matrix,target,i+1,j);//向下递归
if(j<matrix[0].size()-1)
search(matrix,target,i,j+1);//向右递归
}
else matrix[i][j]=-2;//做标记
}
};
``````