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

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

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

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

1. 暴力求解

两重循环，时间复杂度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. Z字形双指针

由于二维数组在行列上分别满足升序，可以用两个指针分别找出其在行与列上的位置
行从前往后遍历，列从后往前遍历，之所以不能同时一个方向，是与target比较时，无法决定先移动哪个指针
时间复杂度为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. 回溯法（深度优先）

递归向右和向下，对于遍历过的路径做标记防止重复
时间复杂度应该为O(m*n),但不知道为什么实际执行时性能比方法二还好

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;//做标记
    }
};