Set Matrix Zeroes
最后更新于：2022-04-01 22:55:44
## 一.题目描述
Given a `m*n` matrix, if an element is `0`, set its entire row and column to `0`. Do it in place.
Follow up: Did you use extra space?
A straight forward solution using `O(mn)` space is probably a bad idea.
A simple improvement uses `O(m + n)` space, but still not the best solution.
Could you devise a constant space solution?
## 二.题目分析
该题目最直观的解法就是开辟一个新的矩阵，当原矩阵存在零元素的时候，就将新矩阵的对应行和列置为零。这样空间复杂度较高，也是题目不允许的。
若要做到空间复杂度为常数，我的做法是就是利用矩阵的第一行和第一列来作为标记使用，这样便不用开辟新的存储空间。具体方法：
1. 先确定第一行和第一列是否需要清零，即：遍历第一行中是否有`0`，也同时记下第一列中有没有`0`。在以下代码中，使用bool型变量`x_key`和`y_key`分别记录第一行和第一列的情况；
2. 扫描剩下的矩阵元素，如果遇到了`0`，就将该元素所对应的第一行和第一列上的元素赋值为`0`；
3. 在遍历完二维数组后，就可以根据第一行和第一列的信息，将剩下的矩阵元素进行赋值。拿第一行为例，如果扫描到第`i`个元素为`0`，就将二维数组的第`i`列全部置`0`；
4. 最后，根据1中bool型变量`x_key`和`y_key`的值，处理第一行和第一列。如果最开始得到的第一行中有`0`的话，就整行清零，对第一列也采取同样的处理。
## 三.示例代码
第一种方法如下：
~~~
#include
using namespace std;
class Solution
{
public:
// 时间复杂度O(m * n)，空间复杂度O(m + n)
void setZeros(vector >& matrix)
{
const size_t x = matrix.size();
const size_t y = matrix[0].size();
if (x == 0 || y == 0) return;
vector rowRes(x, false);
vector colRes(y, false);
for (size_t i = 0; i < x; i++)
{
for (size_t j = 0; j < y; j++)
{
if (matrix[i][j] == 0)
rowRes[i] = colRes[j] = true;
}
}
// set zero
for (size_t i = 0; i < x; i++)
{
if (rowRes[i])
for (size_t k = 0; k < x; k++)
matrix[i][k] = 0;
}
for (size_t j = 0; j < y; j++)
{
if (colRes[j])
for (size_t k = 0; k < x; k++)
matrix[k][j] = 0;
}
}
};
~~~
以上方法的空间复杂度为`O(m + n)`，并不能达到题目要求的最终要求。
**第二种方法**如下：
~~~
#include
using namespace std;
class Solution
{
public:
void setZerosBetter(vector >& matrix)
{
const size_t x = matrix.size();
const size_t y = matrix[0].size();
bool x_key = false, y_key = false;
if (x == 0 || y == 0) return;
for (size_t i = 0; i < y; i++)
{
if (matrix[0][i] == 0)
{
x_key = true;
break;
}
}
for (size_t i = 0; i < x; i++)
{
if (matrix[i][0] == 0)
{
y_key = true;
break;
}
}
for (size_t i = 0; i < x; i++)
{
for (size_t j = 0; j < y; j++)
{
if (matrix[i][j] == 0 && i > 0 && j > 0)
{
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// 调整1~x行、1~y列的元素
for (size_t i = 1; i < x; i++)
if (matrix[i][0] == 0)
{
for (size_t k = 1; k < y; k++)
matrix[i][k] = 0;
}
for (size_t j = 1; j < y; j++)
if (matrix[0][j] == 0)
{
for (size_t k = 1; k < x; k++)
matrix[k][j] = 0;
}
// 最后调整第一行第一列
if (y_key)
for (size_t k = 0; k < x; k++)
matrix[k][0] = 0;
if (x_key)
for (size_t k = 0; k < y; k++)
matrix[0][k] = 0;
}
};
~~~
## 四.小结
这道题如果只是仅仅想实现功能的话，不需要什么技巧，只有提高对空间复杂度的要求才能体现出算法设计的思想。
';