LeetCode 热题 100-矩阵

矩阵置零

分析

• 一个直观的解决方案是使用 O(mn) 的额外空间：即用一个$m \times n$的数组保存原数组。
• 一个简单的改进方案是使用 O(m + n) 的额外空间：即用两个标记数组分别记录每一行和每一列是否有零出现。

可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool col0 = false, row0 = false;

        // 初始化两个变量
        for(int i = 0; i < m; i++){
            if(matrix[i][0] == 0){
                col0 = true;
                break;
            }
        }
        for(int j = 0; j < n; j++){
            if(matrix[0][j] == 0){
                row0 = true;
                break;
            }
        }

        // 初始化第一行和第一列
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // 置0
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(!matrix[i][0] || !matrix[0][j]){
                    matrix[i][j] = 0;
                }
            }
        }

        // 处理第一行和第一列
        if(col0){
            for(int i = 0; i < m; i++){
                matrix[i][0] = 0;
            }
        }
        if(row0){
            for(int j = 0; j < n; j++){
                matrix[0][j] = 0;
            }
        }
    }
};

• 时间复杂度：O(mn)
• 空间复杂度：O(1)

这是世界上最无聊的题目。

螺旋矩阵

模拟

对矩阵进行模拟，每次更新边界位置，初始时向右走，当i == right，开始调整方向向下走，此时对i进行枚举，当i == down，调整方向向左走，枚举j，当i == left，调整方向向上走，对i进行枚举，当i == up，再次向右走。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> res;
        // 定义边界
        int up = 0, down = m-1, left = 0, right = n-1;

        while(1){
            // 向右走
            for(int i = left; i <= right; i++){
                res.push_back(matrix[up][i]);
            }
            // 向下走
            up += 1;
            // 判断边界
            if(up > down){
                break;
            }
            for(int i = up; i <= down; i++){
                res.push_back(matrix[i][right]);
            }
            // 向左走
            right -= 1;
            if(right < left){
                break;
            }
            for(int i = right; i >= left; i--){
                res.push_back(matrix[down][i]);
            }
            // 向上走
            down -= 1;
            if(down < up){
                break;
            }
            for(int i = down; i >= up; i--){
                res.push_back(matrix[i][left]);
            }
            // 向右走
            left += 1;
            if(left > right){
                break;
            }
        }
        return res;
    }
};

• 时间复杂度：O(mn)
• 空间复杂度：O(1)，不计返回的答案数组。

旋转图像

模拟

对于位置(i,j)上的元素，其旋转后会放置在(j,n-i-1)的位置上，而原本(j,n-i-1)的位置上，会旋转到(n-i-1,n-j-1)；(n-i-1,n-j-1)会旋转到(n-j-1, i)，(n-j-1, i)会旋转到(i, j)。因此只需要一个临时变量存储循环中的元素即可。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < n / 2; i++){
            for(int j = 0; j < (n+1)/2; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-j-1][i];
                matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
                matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
                matrix[j][n-i-1] = temp;
            }
        }
    }
};

• 时间复杂度：$O(n^2)$
• 空间复杂度：O(1)

置换+水平翻转

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 置换
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // 水平翻转
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n/2; j++){
                swap(matrix[i][j], matrix[i][n-j-1]);
            }
        }
    }
};

• 时间复杂度：$O(n^2)$
• 空间复杂度：O(1)

搜索二维矩阵II

Z字形查找

z字形查找方法，从矩阵右上角进行搜索:

• matrix[i][j] == target，搜索完成。
• matrix[i][j] > target，j–。
• matrix[i][j] < target，i++。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        // 初始化下标为右上角
        int i = 0, j = n - 1;
        while(i < m && j >= 0){
            if(matrix[i][j] == target){
                return true;
            }else if(matrix[i][j] > target){
                j--;
            }else{
                i++;
            }
        }

        return false;
    }
};

• 时间复杂度：O(m+n)
• 空间复杂度：O(1)