当前位置：首页 > news >正文

【每日一好题】这么经典的题你不能不会：矩阵置零

news 来源：原创 2024/4/27 6:24:07

文章目录

🍁前言

🧧一、题目描述

🏮二、思路解析（最优解法）

🧨三、代码实现（内有超详细的注释）

🦀总结

🍁前言

大家好啊，我是不一样的烟火a，今天我要为大家分享一道好题，这道题也是一道常考题，所以大家务必掌握哦。为了避免以后忘了时再想看就找不到了，所以建议收藏。🦀最后提前祝大家国庆节快乐。

🧧一、题目描述

给定一个 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]]
提示：

m == matrix.length
n == matrix[0].length
1 <= m， n <= 200
-2^31 <= matrix[i][j] <= 2^31 - 1

进阶：

一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

🏮二、思路解析（最优解法）

思路：

我们可以用两个数组分别标记矩阵里面0元素的横坐标和纵坐标。我们用两个数组的下标来代替矩阵里面0元素的下标即可，把两个数组的某个位置的元素置为0即为标记。我们遍历一遍矩阵，遇到0元素，我们就将两个数组对应下标位置设为0进行标记。

我们将矩阵中所有0元素的横纵坐标都标记后，我们这时再遍历一遍矩阵，如果发现当前元素的横坐标或者纵坐标被标记过，那么就将当前元素设置为0。

但是我们如果单独创建2个数组来标记0元素的横纵坐标的话，空间复杂度就为O(m + n) 了，所以我们可以直接将矩阵的第一行用来标记0元素的横坐标，用矩阵的第一列来标记0元素的纵坐标。这样就可以将空间复杂度降为O(1)了。但是我们这时又需要考虑第一行或者第一列是否本身就存在0元素，如果第一行或第一列本身就存在0元素，我们就要将第一列或第一行的所有元素置为0，所以我们需要设置2个flag来标记一下第一行和第一列是否本身就存在0元素。如果我们再想一想，就可以发现，我们其实只用设置一个flag来标记第一列是否本身就存在0元素即可，因为第一列的第一个元素就可以当flag用，如果第一行本身存在0元素，我们在遍历第一行的时候就会将第一列第一个元素标记为0，这样就节省了一个变量的大小。

解题步骤：

1.初始状态：由于第一列中本身就存在0元素，所以我们将flag设置为true，到最后我们就会将第一列所有元素置成0。

2.我们用第一列和第一行来标记0元素的横纵坐标。

3.我们从最后一行，每行的第二列开始遍历矩阵，只要当前元素的横纵坐标有一个被标记，我们就将当前元素置为0。（为什么要从最后一行开始遍历：我们遍历的时候需要从最后一行向上遍历，不要忘我们第一行是用来标记0元素的横坐标的，如果从第一行开始遍历，就有可能将标记的0元素横坐标改变。为什么要从第二列开始遍历：同样第一列是用来存储0元素的纵坐标的，所以我们等一行的其他列都遍历完后再回过头来看第一列，当一行的其他列都遍历完，最后我们判断flag是否为true，也就是判断第一列原本有没有0元素存在，如果flag为true，那么我们就将第一列的元素置为0。）

🧨三、代码实现（内有超详细的注释）

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        // int flag_row0 = false; // 用于标记第一行是否有0，可以用第一列的第一个元素代替，从而减少了一个变量


        int flag_col0 = false; // 用于标记第一列是否有0
        int row = matrix.size(); // 一共有多少行
        int col = matrix[0].size(); // 一共有多少列

        // 遍历一遍矩阵
        // 用第一行和第一列标记矩阵中0元素的坐标
        // 并且判断第一列是否本身就存在0
        for (int i = 0; i < row; ++i)
        {
            // 只要第一列存在一个0，就将第一列标记
            if (!matrix[i][0])
            {
                flag_col0 = true;
            }

            // 标记每个0元素的下标
            // 由于第一列已经单独判断了，所以这里只用从第二列开始遍历
            for (int j = 1; j < col; ++j)
            {
                // 如果当前元素为0，就将它的横纵坐标分别在第一行和第一列中进行标记
                if (matrix[i][j] == 0)
                {
                    // 注意：这里的i为纵坐标，j为横坐标
                    matrix[0][j] = 0; // 第一行用于标记横坐标
                    matrix[i][0] = 0; // 第一列用于标记纵坐标
                }
            }
        }

        // 再遍历一遍矩阵，只要当前元素的横坐标、纵坐标有一个被标记过，就将其置为0
        // 注意：这时遍历时就不能从第一列开始遍历了，如果第一列本身存在0，我们遍历完第一列就将第一列全部置成0了，导致我们刚才标记的坐标改变
        // 所以我们需要从后向前遍历。
        // 每行的第一个元素也要最后判断，如果先判断的话就跟先遍历第一行是一样的了
        // 如果第一列本身存在0，那么从每行第一个元素开始遍历，就会将第一个元素置成0，导致我们标记的坐标改变。

        for (int i = row - 1; i >= 0; --i)
        {
            // 由于下面会单独判断第一列元素，所以这里还是从第二列开始遍历
            for (int j = 1; j < col; ++j)
            {
                // 如果当前元素的横坐标、纵坐标有一个被标记过，就将其置为0
                if (!matrix[0][j] || !matrix[i][0])
                {
                   matrix[i][j] = 0;
                }
            }

            // 判断第一列是否本身就有0，如果有就将第一列的元素置成0，如果没有就不管了
            if (flag_col0)
            {
                 matrix[i][0] = 0;
            }
        }
    }
};