【3.21】LeetCode每日一题· 矩阵置零

2021年03月21日 12时05分

标签： LeetCode 数组

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

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

#### 示例1
![](https://assets.leetcode.com/uploads/2020/08/17/mat1.jpg)
```
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
```

#### 示例2
![](https://assets.leetcode.com/uploads/2020/08/17/mat2.jpg)
```
输入：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
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/set-matrix-zeroes/ "题目链接")

## O(mn)空间方法
将原数组拷贝一份，遍历拷贝的数组，如果遇到0，则将原数组该元素所在行和列全置为0即可，在此不在列出代码。

## O(m+n)空间方法
对于数组中值为0的元素，记录它所在的行和列，那么最后所有记录的行和列上的元素都应置为0。
1. 使用两个布尔数组`row[]`和`col[]`。其中`row[]`的长度和矩阵的行数`m`相等，`col[]`的长度和矩阵的宽`n`相等，元素的初始值均为`false`。
2. 当遍历到数组中某一元素`matrix[i][j] == 0`时，就`row[i] = col[j] = true`
3. 最后遍历`row[]`和`col[]`
	* 对于某一`row[i] == 0`，将所有`matrix[i][col](0 <= col < n)`置为0。
	* 对于某一`col[j] == 0`，将所有`matrix[row][j](0 <= row < m)`置为0。

### 代码
```cpp
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        vector<int> rows(matrix.size()), cols(matrix[0].size());
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(!matrix[i][j]){
                    rows[i] = 1;
                    cols[j] = 1;
                }
            }
        }
        for(int i = 0; i < rows.size(); i++){
            if(rows[i]){
                for(int col = 0; col < cols.size(); col++){
                    matrix[i][col] = 0;
                }
            }
        }
        for(int j = 0; j < cols.size(); j++){
            if(cols[j]){
                for(int row = 0; row < rows.size(); row++){
                    matrix[row][j] = 0;
                }
            }
        }
    }
};
```
### 用时和内存
> 执行用时：16 ms，在所有 C++提交中击败了80.35%的用户
> 内存消耗：12.9 MB，在所有 C++提交中击败了53.31%的用户

## O(1)空间方法
如果将矩阵的第一行和第一列（即下标为0的行和列）除去，那么新矩阵中对于值为0的元素，将其位置投影到原矩阵中的第一行和第一列中去，该投影位置的值一定为0。换句话说，如果
```cpp
matrix[i][j] == 0, 1 <= i < m && 1 <= j < n
```
那么有
```cpp
matrix[i][0] = matrix[0][j] = 0
```
因此，我们可以使用矩阵的第一行和第一列分别作为$$O(m+n)$$空间方法中的`row[]`和`col[]`数组。但是此时尚未考虑第一行和第一列元素的情况，因此使用两个标记变量`flag_col0`和`flag_row0`记录原矩阵的第一行和第一列是否存在0元素。
这样，我们首先根据`matrix[i][0] = matrix[0][j]`的情况更新`1 <= i < m && 1 <= j < n`范围内的子数组，然后根据`flag_col0`和`flag_row0`更新第一行和第一列即可。
### 代码
```cpp
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int flag_row0 = false, flag_col0 = false;
        for(int i = 0; i < matrix.size(); i++){
            if(!matrix[i][0]) flag_row0 = true;
        }
        for(int j = 0; j < matrix[0].size(); j++){
            if(!matrix[0][j]) flag_col0 = true;
        }
        for(int i = 1; i < matrix.size(); i++){
            for(int j = 1; j < matrix[0].size(); j++){
                if(!matrix[i][j]){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

for(int i = 1; i < matrix.size(); i++){
            if(!matrix[i][0]){
                for(int col = 0; col < matrix[0].size(); col++){
                    matrix[i][col] = 0;
                }
            }
        }

for(int j = 1; j < matrix[0].size(); j++){
            if(!matrix[0][j]){
                for(int row = 0; row < matrix.size(); row++){
                    matrix[row][j] = 0;
                }
            }
        }

if(flag_row0){
            for(int row = 0; row < matrix.size(); row++){
                matrix[row][0] = 0;
            }
        }
        if(flag_col0){
            for(int col = 0; col < matrix[0].size(); col++){
                matrix[0][col] = 0;
            }
        }
    }
};
```
### 用时和内存
> 执行用时：12 ms，在所有 C++提交中击败了94.77%的用户
> 内存消耗：12.9 MB，在所有 C++提交中击败了56.93%的用户

## 进一步的优化
我们可以只使用一个标记变量，标记第一列是否原本存在0，然后`matrix[0][0]`就可以标记第一行是否原本存在0。
最后遍历矩阵`matrix[i][j]`，如果`matrix[i][0] == 0 || matrix[j][0] == 0`，那么有`matrix[i][j] = 0`。
但是，如果从左到右，从上往下进行遍历，在`matrix[0][0] == 0`的情况下，会提前将`matrix[0][j]`置为0，从而除第一列以外的所有元素都会被置为0。为了防止这一情况发生，在行上，需要从下往上遍历。
### 代码
```cpp
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int flag_row0 = false;
        for(int i = 0; i < matrix.size(); i++){
            if(!matrix[i][0]) flag_row0 = true;
            for(int j = 1; j < matrix[0].size(); j++){
                if(!matrix[i][j]){
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for(int i = matrix.size()-1; i >= 0; --i){
            for(int j = 1; j < matrix[0].size(); j++){
                if(!matrix[i][0] || !matrix[0][j]){
                    matrix[i][j] = 0;
                }
            }
            if(flag_row0){
                matrix[i][0] = 0;
            }
        }
    }
};
```
### 用时和内存
> 执行用时：12 ms，在所有 C++提交中击败了94.77%的用户
> 内存消耗：12.9 MB，在所有 C++提交中击败了71.20%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.21】LeetCode每日一题· 矩阵置零

所有评论

暂无评论

新增评论