矩阵置零的三种解法

😎 作者介绍：我是程序员行者孙，一个热爱分享技术的制能工人。计算机本硕，人工制能研究生。公众号：AI Sun，视频号：AI-行者Sun
🎈 本文专栏：本文收录于《深入浅出算法》系列专栏，相信一份耕耘一份收获，我会系统全面的分享算法课程，届时可以拳打字节，脚踢腾讯
🤓 欢迎大家关注其他专栏，我将分享Web前后端开发、人工智能、机器学习、深度学习从0到1系列文章。
🖥 随时欢迎您跟我沟通，一起交流，一起成长、进步！

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

正常思路不难，思路二三怎么说呢，有点shi山换空间的感觉，代码可读性太差了（上班这么写就等着挨骂），但是想法值得借鉴

思路 1：两次遍历

1. 记录信息：首先遍历矩阵，记录下所有为0的元素的行列索引。你可以使用两个哈希表或数组来记录这些信息，一个用于行，一个用于列。
2. 标记行和列：创建两个布尔数组（或者在原矩阵中使用额外的一行和一列作为标记），用来标记哪些行和列应该被置零。
3. 置零操作：再次遍历矩阵，根据标记数组，将所有应该置零的行和列的元素都设置为0。

代码：

class Solution {
public:
    // setZeroes函数用于将矩阵中的所有0元素所在行和列置零
    void setZeroes(vector<vector<int>>& matrix) {
        // 获取矩阵的行数和列数
        int n = matrix.size(), m = matrix[0].size();
        
        // 初始化行和列的状态数组，用于标记哪些行和列需要置零
        vector<int> row(n, false), col(m, false);
        
        // 第一次遍历，标记需要置零的行和列
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                // 如果当前元素为0，则标记对应行和列
                if(matrix[i][j] == 0) {
                    row[i] = true; // 标记第i行需要置零
                    col[j] = true; // 标记第j列需要置零
                }
            }
        }
        
        // 第二次遍历，根据标记结果将矩阵中对应位置的元素置零
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                // 如果当前行或列被标记，则将元素置零
                if(row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

思路 2：一次遍历 + 行/列操作

1. 标记行和列：在一次遍历中，当遇到一个为0的元素时，立即标记对应的行和列。这可以通过在行和列的首尾元素中设置一个标记值来实现（例如，将行的第一个元素和列的最后一个元素设为一个特定的非零值，如-1）。
2. 置零操作：在完成标记后，再次遍历矩阵，根据标记值来将整行或整列置零。

代码：

class Solution {
public:
    // setZeroes函数用于将矩阵中的所有0元素所在行和列置零
    void setZeroes(vector<vector<int>>& matrix) {
        // 获取矩阵的行数m和列数n
        int m = matrix.size();
        int n = matrix[0].size();
        
        // 标记第一行和第一列是否包含0
        int flag_col0 = false, flag_row0 = false;
        // 遍历第一行和第一列，如果发现0，则设置相应的标记为true
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) { // 如果第一列的某个元素为0
                flag_col0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (!matrix[0][j]) { // 如果第一行的某个元素为0
                flag_row0 = true;
            }
        }
        
        // 遍历矩阵的剩余部分（排除第一行和第一列）
        // 如果发现0，将对应的第一行和第一列的元素置零
        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]) { // 检查第一行或第一列的对应元素是否为0
                    matrix[i][j] = 0; // 将当前元素置零
                }
            }
        }
        
        // 最后，根据之前的标记，将第一行和第一列的所有元素置零
        // 这一步是必要的，因为第一行和第一列的元素可能在之前的遍历中没有被检查
        if (flag_col0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0; // 如果第一列有0，将第一列所有元素置零
            }
        }
        if (flag_row0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0; // 如果第一行有0，将第一行所有元素置零
            }
        }
    }
};

思路 3：原地标记 + 矩阵重构

1. 原地标记：遍历矩阵，对于每个元素，如果它为0，则直接将其所在行和列的其他元素也设置为0。
2. 矩阵重构：在完成置零操作后，遍历矩阵，对于每个元素，如果它不在原地被置零（即它不在标记的行或列中），则将其复制到一个新的矩阵中，从而得到最终的结果。

class Solution {
public:
    // setZeroes函数用于将矩阵中的所有0元素所在行和列置零
    void setZeroes(vector<vector<int>>& matrix) {
        // 获取矩阵的行数m和列数n
        int m = matrix.size();
        int n = matrix[0].size();
        // flag_col0用于标记第一列中是否存在0
        int flag_col0 = false;
        
        // 遍历矩阵的每一行
        for (int i = 0; i < m; i++) {
            // 如果第一行的某个元素为0，则将flag_col0设置为true
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
            // 遍历矩阵的每一列，跳过第一列
            for (int j = 1; j < n; j++) {
                // 如果当前元素为0，则将对应行的第一列元素和对应列的第一行元素设置为0
                if (!matrix[i][j]) {
                    matrix[i][0] = 0; // 将当前行的第一列元素置零
                    matrix[0][j] = 0; // 将当前列的第一行元素置零
                }
            }
        }
        
        // 从矩阵的底部开始向上遍历
        for (int i = m - 1; i >= 0; i--) {
            // 遍历矩阵的每一列，跳过第一列
            for (int j = 1; j < n; j++) {
                // 如果当前行的第一列元素或当前列的第一行元素已置零，则将当前元素置零
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
            // 如果第一列中存在0，且当前行是第一行，则将第一列的当前行元素置零
            if (flag_col0) {
                matrix[i][0] = 0;
            }
        }
    }
};