73. Set Matrix Zeroes

題目網址：https://leetcode.cn/problems/set-matrix-zeroes/

題意：給一 m x n 的 matrix, 若其中一元素為0, 將其所在列和行的所有元素都設為0。

注意：請使用 in-place 演算法

進階：

• 用 O(mn) space 的直覺作法似乎是個壞主意
• 設計 O(m + n) space 的演算法，但這仍然不是最好的解決方案
• 設計 O(1) space 的演算法

Solution 1：

想法：分別用 rows, cols 來記錄哪些 row, col 上的元素要設為 0

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        const int m = matrix.size(), n = matrix[0].size();
        vector<int> rows(m, 0), cols(n, 0);

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

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (rows[i] || cols[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

• time：$O(m \cdot n)$ ➔ 遍歷 matrix
• space：$O(m + n)$ ➔ rows 和 cols

Solution 2：

想法：用 col0, row0 分別記錄第一行、第一列是否有元素為 0, 然後用 matrix 中的第一行、第一列分別紀錄該行、列是否有元素為 0
（用 matrix 中的第一行、第一列取代 Solution 1 的 rows、cols ）

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

        // 記錄第一行是否有元素為0
        for (int i = 0; i < m; ++i) {
            if (matrix[i][0] == 0) {
                col0 = true;
            }
        }

        // 記錄第一列是否有元素為0
        for (int j = 0; j < n; ++j) {
            if (matrix[0][j] == 0) {
                row0 = true;
            }
        }

        // 用 matrix 中的第一行、第一列分別紀錄該行、列是否有元素為0
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }

        // 根據 matrix[i][0]、matrix[0][j] 是否為0, 來決定是否把 matrix[i][j] 設為0
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 判斷 matrix 的第一行是否要設0
        if (col0) {
            for (int i = 0; i < m; ++i) {
                matrix[i][0] = 0;
            }
        }

        // 判斷 matrix 的第一列是否要設0
        if (row0) {
            for (int j = 0; j < n; ++j) {
                matrix[0][j] = 0;
            }
        }
    }
};

• time：$O(m \cdot n)$ ➔ 遍歷 matrix
• space：$O(1)$ ➔ 只需常數空間