073.矩阵置零

作者：沉默王二
发布时间：2023-02-25T10:45:04.417+0800

---

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

这里给大家解释一下什么是原地算法。假设你现在是一个大厨，对，戴的帽子非常高的那种。但是老板对你有一些苛刻的要求，比如说菜板非常小，但又不给你提供额外的餐盘作为辅助，要你在这个小菜板上切碎很多很多蔬菜，比如说肉丝、葱姜蒜、蒜苔等等。

换句话说，原地算法是指在算法的执行过程中，不需要使用额外的内存空间，而是直接在原始输入数据的存储空间中进行计算。有时候，可能需要牺牲掉一些时间。

难度

中等

示例

示例1：

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

示例2：

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

分析

本题并不算难，读完题目，我们应该很快就能够想到利用两个辅助数组，分别来记录该行/列是否有0出现过。

然后再遍历所有的元素，按照辅助数组来决定当前位置是否要置换为0。

依照上述的思想，我们可以写出如下的代码：

class Solution {

        int n = matrix.length;        int m = matrix[0].length;        boolean[] zeroInRow = new boolean[n];        boolean[] zeroInLine = new boolean[m];        for(int i = 0;i < n;i++)            for(int j = 0;j < m;j++)                if(matrix[i][j] == 0){                    zeroInRow[i] = true;                    zeroInLine[j] = true;                }        for(int i = 0;i < n;i++)            for(int j = 0;j < m;j++)                if(zeroInRow[i] || zeroInLine[j]){                    matrix[i][j] = 0;                }    }}

这样子确实能够解题，而且效果也不错！

但是，能不能再优化优化？

时间复杂度方面已经优化的余地了，因为必须要对每个元素进行甄别或者修改，所以时间复杂度至少为，那我们就考虑下，能不能对空间复杂度进行优化呢？

当前采取的方法，需要两个辅助数组来帮助我们定位0，这样子的话，辅助数据的空间就会随着矩阵大小而增加，有没有办法能够在常数的空间范围内，将这道题目解决呢？

我们来观察一下，标记数组是一个boolean类型的数组，每一位都由 0 和 1 组成，很容易使得我们联想到另外一个同样由这两个组成的东西—— 二进制 ！！！！

是的，我们可以用两个二进制来描述这个boolean数组！

而描述一个二进制数，只需要一个整型即可，于是乎，我们就能写出这样子的代码：

class Solution {

        long n = 0;        long m = 0;        for(int i = 0;i < matrix.length;i++)            for(int j = 0;j < matrix[0].length;j++)                if(matrix[i][j] == 0){                    n |= 1L << (i);                    m |= 1L << (j);                }        for(int i = 0;i < matrix.length;i++)            for(int j = 0;j < matrix[0].length;j++)                if((((n >> i) & 1) != 0) || (((m >> j) & 1) != 0)){                    matrix[i][j] = 0;                }    }}

此时，原先代码中用于标记的boolean数组被我们用n,m取代了。

但是！！！

这份代码并不能通过所有的测试点，为什么呢？

原因在于 整型的限制 ！！！

我们知道，整型的指示范围在-2147483648~2147483647之间，也就是，所以当矩阵的大小超过32的时候，我们的范围就不够用了，那么长整型long呢，虽然大了很多，可惜仍然不能满足需求，所以我们必须另寻它路。

其实我们还能利用——每行每列的第0个元素！

如果我们提前利用两个变量来记录第0行以及第0列中是否含有0，这时候，第0行和第0列都能为我们所用，用来标记当前行/列中是否存在0，也就是 把第0行和第0列作为一开始的两个标记数组，然后再按照这个信息来判断每个位置需不需要修改为0。

最后再按照提前准备的两个变量判断需不需要把第0行和第0列修改为0。

class Solution {

        boolean row0 = false;        boolean line0 = false;        for (int[] ints : matrix)            if (ints[0] == 0) {                row0 = true;                break;            }        for(int i = 0;i < matrix[0].length;i++)            if(matrix[0][i] == 0){                line0 = true;                break;            }        for(int i = 1;i < matrix.length;i++)            for(int j = 1;j < matrix[0].length;j++){                if(matrix[i][j] == 0) {                    matrix[0][j] = 0;                    matrix[i][0] = 0;                }            }        for(int i = 1;i < matrix.length;i++)            for(int j = 1;j < matrix[0].length;j++){                if(matrix[0][j] == 0 || matrix[i][0] == 0) {                    matrix[i][j] = 0;                }            }        for(int i = 0;i < matrix.length;i++){            if(row0)                matrix[i][0] = 0;        }        for(int i = 0;i < matrix[0].length;i++){            if(line0)                matrix[0][i] = 0;        }    }}

这时候我们就真正做到了利用常数级别的空间复杂度，帅气顺利地解决本题！

总结

其实算法就是用空间换取时间，用时间换取空间，或者是不断优化，利用更少的空间、更少的时间来实现我们的目的。

力扣链接：https://leetcode.cn/problems/set-matrix-zeroes/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

这里给大家解释一下什么是原地算法。假设你现在是一个大厨，对，戴的帽子非常高的那种。但是老板对你有一些苛刻的要求，比如说菜板非常小，但又不给你提供额外的餐盘作为辅助，要你在这个小菜板上切碎很多很多蔬菜，比如说肉丝、葱姜蒜、蒜苔等等。

换句话说，原地算法是指在算法的执行过程中，不需要使用额外的内存空间，而是直接在原始输入数据的存储空间中进行计算。有时候，可能需要牺牲掉一些时间。

难度

中等

示例

示例1：

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

示例2：

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

分析

本题并不算难，读完题目，我们应该很快就能够想到利用两个辅助数组，分别来记录该行/列是否有0出现过。

然后再遍历所有的元素，按照辅助数组来决定当前位置是否要置换为0。

依照上述的思想，我们可以写出如下的代码：

class Solution {

        int n = matrix.length;        int m = matrix[0].length;        boolean[] zeroInRow = new boolean[n];        boolean[] zeroInLine = new boolean[m];        for(int i = 0;i < n;i++)            for(int j = 0;j < m;j++)                if(matrix[i][j] == 0){                    zeroInRow[i] = true;                    zeroInLine[j] = true;                }        for(int i = 0;i < n;i++)            for(int j = 0;j < m;j++)                if(zeroInRow[i] || zeroInLine[j]){                    matrix[i][j] = 0;                }    }}

这样子确实能够解题，而且效果也不错！

但是，能不能再优化优化？

时间复杂度方面已经优化的余地了，因为必须要对每个元素进行甄别或者修改，所以时间复杂度至少为，那我们就考虑下，能不能对空间复杂度进行优化呢？

当前采取的方法，需要两个辅助数组来帮助我们定位0，这样子的话，辅助数据的空间就会随着矩阵大小而增加，有没有办法能够在常数的空间范围内，将这道题目解决呢？

我们来观察一下，标记数组是一个boolean类型的数组，每一位都由 0 和 1 组成，很容易使得我们联想到另外一个同样由这两个组成的东西—— 二进制 ！！！！

是的，我们可以用两个二进制来描述这个boolean数组！

而描述一个二进制数，只需要一个整型即可，于是乎，我们就能写出这样子的代码：

class Solution {

        long n = 0;        long m = 0;        for(int i = 0;i < matrix.length;i++)            for(int j = 0;j < matrix[0].length;j++)                if(matrix[i][j] == 0){                    n |= 1L << (i);                    m |= 1L << (j);                }        for(int i = 0;i < matrix.length;i++)            for(int j = 0;j < matrix[0].length;j++)                if((((n >> i) & 1) != 0) || (((m >> j) & 1) != 0)){                    matrix[i][j] = 0;                }    }}

此时，原先代码中用于标记的boolean数组被我们用n,m取代了。

但是！！！

这份代码并不能通过所有的测试点，为什么呢？

原因在于 整型的限制 ！！！

我们知道，整型的指示范围在-2147483648~2147483647之间，也就是，所以当矩阵的大小超过32的时候，我们的范围就不够用了，那么长整型long呢，虽然大了很多，可惜仍然不能满足需求，所以我们必须另寻它路。

其实我们还能利用——每行每列的第0个元素！

如果我们提前利用两个变量来记录第0行以及第0列中是否含有0，这时候，第0行和第0列都能为我们所用，用来标记当前行/列中是否存在0，也就是 把第0行和第0列作为一开始的两个标记数组，然后再按照这个信息来判断每个位置需不需要修改为0。

最后再按照提前准备的两个变量判断需不需要把第0行和第0列修改为0。

class Solution {

        boolean row0 = false;        boolean line0 = false;        for (int[] ints : matrix)            if (ints[0] == 0) {                row0 = true;                break;            }        for(int i = 0;i < matrix[0].length;i++)            if(matrix[0][i] == 0){                line0 = true;                break;            }        for(int i = 1;i < matrix.length;i++)            for(int j = 1;j < matrix[0].length;j++){                if(matrix[i][j] == 0) {                    matrix[0][j] = 0;                    matrix[i][0] = 0;                }            }        for(int i = 1;i < matrix.length;i++)            for(int j = 1;j < matrix[0].length;j++){                if(matrix[0][j] == 0 || matrix[i][0] == 0) {                    matrix[i][j] = 0;                }            }        for(int i = 0;i < matrix.length;i++){            if(row0)                matrix[i][0] = 0;        }        for(int i = 0;i < matrix[0].length;i++){            if(line0)                matrix[0][i] = 0;        }    }}

这时候我们就真正做到了利用常数级别的空间复杂度，帅气顺利地解决本题！

总结

其实算法就是用空间换取时间，用时间换取空间，或者是不断优化，利用更少的空间、更少的时间来实现我们的目的。

力扣链接：https://leetcode.cn/problems/set-matrix-zeroes/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记，数学表达公式也能显示出来），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

这里给大家解释一下什么是原地算法。假设你现在是一个大厨，对，戴的帽子非常高的那种。但是老板对你有一些苛刻的要求，比如说菜板非常小，但又不给你提供额外的餐盘作为辅助，要你在这个小菜板上切碎很多很多蔬菜，比如说肉丝、葱姜蒜、蒜苔等等。

换句话说，原地算法是指在算法的执行过程中，不需要使用额外的内存空间，而是直接在原始输入数据的存储空间中进行计算。有时候，可能需要牺牲掉一些时间。

难度

中等

示例

示例1：

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

示例2：

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

分析

本题并不算难，读完题目，我们应该很快就能够想到利用两个辅助数组，分别来记录该行/列是否有0出现过。

然后再遍历所有的元素，按照辅助数组来决定当前位置是否要置换为0。

依照上述的思想，我们可以写出如下的代码：

class Solution {

        int n = matrix.length;        int m = matrix[0].length;        boolean[] zeroInRow = new boolean[n];        boolean[] zeroInLine = new boolean[m];        for(int i = 0;i < n;i++)            for(int j = 0;j < m;j++)                if(matrix[i][j] == 0){                    zeroInRow[i] = true;                    zeroInLine[j] = true;                }        for(int i = 0;i < n;i++)            for(int j = 0;j < m;j++)                if(zeroInRow[i] || zeroInLine[j]){                    matrix[i][j] = 0;                }    }}

这样子确实能够解题，而且效果也不错！

但是，能不能再优化优化？

时间复杂度方面已经优化的余地了，因为必须要对每个元素进行甄别或者修改，所以时间复杂度至少为，那我们就考虑下，能不能对空间复杂度进行优化呢？

当前采取的方法，需要两个辅助数组来帮助我们定位0，这样子的话，辅助数据的空间就会随着矩阵大小而增加，有没有办法能够在常数的空间范围内，将这道题目解决呢？

我们来观察一下，标记数组是一个boolean类型的数组，每一位都由 0 和 1 组成，很容易使得我们联想到另外一个同样由这两个组成的东西—— 二进制 ！！！！

是的，我们可以用两个二进制来描述这个boolean数组！

而描述一个二进制数，只需要一个整型即可，于是乎，我们就能写出这样子的代码：

class Solution {

        long n = 0;        long m = 0;        for(int i = 0;i < matrix.length;i++)            for(int j = 0;j < matrix[0].length;j++)                if(matrix[i][j] == 0){                    n |= 1L << (i);                    m |= 1L << (j);                }        for(int i = 0;i < matrix.length;i++)            for(int j = 0;j < matrix[0].length;j++)                if((((n >> i) & 1) != 0) || (((m >> j) & 1) != 0)){                    matrix[i][j] = 0;                }    }}

此时，原先代码中用于标记的boolean数组被我们用n,m取代了。

但是！！！

这份代码并不能通过所有的测试点，为什么呢？

原因在于 整型的限制 ！！！

我们知道，整型的指示范围在-2147483648~2147483647之间，也就是，所以当矩阵的大小超过32的时候，我们的范围就不够用了，那么长整型long呢，虽然大了很多，可惜仍然不能满足需求，所以我们必须另寻它路。

其实我们还能利用——每行每列的第0个元素！

如果我们提前利用两个变量来记录第0行以及第0列中是否含有0，这时候，第0行和第0列都能为我们所用，用来标记当前行/列中是否存在0，也就是 把第0行和第0列作为一开始的两个标记数组，然后再按照这个信息来判断每个位置需不需要修改为0。

最后再按照提前准备的两个变量判断需不需要把第0行和第0列修改为0。

class Solution {

        boolean row0 = false;        boolean line0 = false;        for (int[] ints : matrix)            if (ints[0] == 0) {                row0 = true;                break;            }        for(int i = 0;i < matrix[0].length;i++)            if(matrix[0][i] == 0){                line0 = true;                break;            }        for(int i = 1;i < matrix.length;i++)            for(int j = 1;j < matrix[0].length;j++){                if(matrix[i][j] == 0) {                    matrix[0][j] = 0;                    matrix[i][0] = 0;                }            }        for(int i = 1;i < matrix.length;i++)            for(int j = 1;j < matrix[0].length;j++){                if(matrix[0][j] == 0 || matrix[i][0] == 0) {                    matrix[i][j] = 0;                }            }        for(int i = 0;i < matrix.length;i++){            if(row0)                matrix[i][0] = 0;        }        for(int i = 0;i < matrix[0].length;i++){            if(line0)                matrix[0][i] = 0;        }    }}

这时候我们就真正做到了利用常数级别的空间复杂度，帅气顺利地解决本题！

总结

其实算法就是用空间换取时间，用时间换取空间，或者是不断优化，利用更少的空间、更少的时间来实现我们的目的。

力扣链接：https://leetcode.cn/problems/set-matrix-zeroes/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 1800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412