73. 矩阵置零

题意

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

请使用 原地 算法。

这里给大家解释一下什么是原地算法。假设你现在是一个大厨，对，戴的帽子非

常高的那种。但是老板对你有一些苛刻的要求，比如说菜板非常小，但又不给你

提供额外的餐盘作为辅助，要你在这个小菜板上切碎很多很多蔬菜，比如说肉

丝、葱姜蒜、蒜苔等等。

换句话说，原地算法是指在算法的执行过程中，不需要使用额外的内存空间，而

是直接在原始输入数据的存储空间中进行计算。有时候，可能需要牺牲掉一些时

间。

难度

中等

示例

示例 1：

1677292978543-0f6c7610-10f2-42ed-9739-2a89f7c44c07.jpeg

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

输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

1677292986487-9bd9da8c-3c57-4fcc-b584-e87d9f5d3c08.jpeg

输入：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]]

分析

本题并不算难，读完题目，我们应该很快就能够想到利用两个辅助数组，分别来记录该

行/列是否有 0 出现过。

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

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

class Solution {

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

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;

}

}

}

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

1677292996241-96a2f819-eb99-43bf-88c8-c277adce4557.png

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

时间复杂度方面已经优化的余地了，因为必须要对每个元素进行甄别或者修改，所以时间

复杂度至少为$ O(nm) $，那我们就考虑下，能不能对空间复杂度进行优化呢？

当前采取的方法，需要两个辅助数组来帮助我们定位 0，这样子的话，辅助数据的空间就

会随着矩阵大小而增加，有没有办法能够在常数的空间范围内，将这道题目解决呢？

我们来观察一下，标记数组是一个 boolean 类型的数组，每一位都由 0 和 1 组成，很容

易使得我们联想到另外一个同样由这两个组成的东西—— 二进制 ！！！！

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

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

class Solution {

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

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 之间，也就是$ -2{31}至 2{31}-1

$，所以当矩阵的大小超过 32 的时候，我们的范围就不够用了，那么长整型 long 呢，虽

然大了很多，可惜仍然不能满足需求，所以我们必须另寻它路。

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

如果我们提前利用两个变量来记录第 0 行以及第 0 列中是否含有 0，这时候，第 0 行和第

0 列都能为我们所用，用来标记当前行/列中是否存在 0，也就是 把第**0**行和第**0**

列作为一开始的两个标记数组，然后再按照这个信息来判断每个位置需不需要修改为 0。

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

class Solution {

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

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;

}

}

}

1677293009114-ec836be1-fd5e-464e-8684-949ebeaecaa3.png

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

总结

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

少的时间来实现我们的目的。

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