分析

• 本题的考点：数组。

• 因为要使用原地算法，我们用第一行记录对应的每一列是否存在0，用第一列记录每一列是否存在0。如果存在0的话，第一行或者第一列对应位置置为0。

• 这样的话，我们就不知道第一行、第一列是否存在0，因此，最开始需要使用r0、c0记录第一行、第一列是否存在0。

代码

• C++

class Solution {
public:
    void setZeroes(vector<vector<int>> &matrix) {

        if (matrix.empty() || matrix[0].empty()) return;
        int n = matrix.size(), m = matrix[0].size();

        int r0 = 1, c0 = 1;
        for (int i = 0; i < m; i++) if (!matrix[0][i]) r0 = 0;
        for (int i = 0; i < n; i++) if (!matrix[i][0]) c0 = 0;

        for (int i = 1; i < n; i++)  // 第i行是否存在0
            for (int j = 0; j < m; j++)
                if (!matrix[i][j])
                    matrix[i][0] = 0;
        for (int i = 1; i < m; i++)  // 第i列是否存在0
            for (int j = 0; j < n; j++)
                if (!matrix[j][i])
                    matrix[0][i] = 0;

        for (int i = 1; i < n; i++)
            if (!matrix[i][0])
                for (int j = 0; j < m; j++)
                    matrix[i][j] = 0;
        for (int i = 1; i < m; i++)
            if (!matrix[0][i])
                for (int j = 0; j < n; j++)
                    matrix[j][i] = 0;

        if (!r0) for (int i = 0; i < m; i++) matrix[0][i] = 0;
        if (!c0) for (int i = 0; i < n; i++) matrix[i][0] = 0;
    }
};

• Java

class Solution {
    public void setZeroes(int[][] matrix) {

        int n = matrix.length, m = matrix[0].length;

        int r0 = 1, c0 = 1;
        for (int i = 0; i < m; i++) if (matrix[0][i] == 0) r0 = 0;
        for (int i = 0; i < n; i++) if (matrix[i][0] == 0) c0 = 0;

        for (int i = 1; i < n; i++)  // 第i行是否存在0
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == 0)
                    matrix[i][0] = 0;
        for (int i = 1; i < m; i++)  // 第i列是否存在0
            for (int j = 0; j < n; j++)
                if (matrix[j][i] == 0)
                    matrix[0][i] = 0;

        for (int i = 1; i < n; i++)
            if (matrix[i][0] == 0)
                for (int j = 0; j < m; j++)
                    matrix[i][j] = 0;
        for (int i = 1; i < m; i++)
            if (matrix[0][i] == 0)
                for (int j = 0; j < n; j++)
                    matrix[j][i] = 0;

        if (r0 == 0) for (int i = 0; i < m; i++) matrix[0][i] = 0;
        if (c0 == 0) for (int i = 0; i < n; i++) matrix[i][0] = 0;
    }
}

时空复杂度分析

• 时间复杂度：$O(n \times m)$，n、m为行数、列数。

• 空间复杂度：$O(1)$。