Skip to main content

73. 矩阵置零

caution

原题链接：https://leetcode-cn.com/problems/set-matrix-zeroes/

思路​

  • 方法一：

    用一个二维数组存储元素为 0 的位置，然后在根据位置把对应的行和列置零

  • 方法二：

    可以不用二维数组来存储对应的行列，分别用两个数组存储行坐标和列坐标即可。

  • 方法三：

    因为出现在矩阵中间的 0 最终都会修改第一行或者第一列的元素，所以使用第一行和第一列代替标记数组，但是这样会导致第一行和第一列被修改，所以需要额外两个标记变量确认第一行和第一列是否有 0。

代码​

标记矩阵中 0 的坐标位置，并使用二维数组存储。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        vector<vector<int>> res;
        for (int i =0 ; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (matrix[i][j] == 0)
                    res.push_back({i, j});
            }
        }

        for (int i = 0; i < res.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                matrix[res[i][0]][j] = 0;
            }
            for (int j = 0; j < matrix.size(); j++) {
                matrix[j][res[i][1]] = 0;
            }
        }
    }
};

空间复杂度：O(nm)O(nm)

使用两个一维数组存储：

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        vector<int> row;
        vector<int> col;
        for (int i =0 ; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size(); j++) {
                if (matrix[i][j] == 0)
                    row.push_back(i), col.push_back(j);
            }
        }

        for (int i = 0; i < row.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                matrix[row[i]][j] = 0;
            }
        }
        for (int i = 0; i < col.size(); i++) {
            for (int j = 0; j < matrix.size(); j++) {
                matrix[j][col[i]] = 0;
            }
        }
    }
};

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

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false, flag_row0 = false;
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (!matrix[0][j]) {
                flag_row0 = true;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][j]) {
                    matrix[i][0] = matrix[0][j] = 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 (flag_col0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flag_row0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
};

常量空间存储：O(1)O(1)