LeetCode 73. 矩阵置零——每日一题

Love The Way You Lie 2022-11-12 01:38 121阅读 0赞

**上一篇博客：[堆优化版Dijkstra算法][Dijkstra]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 73. 矩阵置零][LeetCode 73.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  示例 1
     *  示例 2
     *  提示
 *  题解
 *   *  暴力解法
     *   *  解题思路
         *  解题代码
     *  优化解法（原地算法）
     *   *  解题思路
         *  解题代码

# 题目信息 #

## 题目描述 ##

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

**进阶：**

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

## 示例 1 ##

![示例1][1]

> **输入：matrix = \[\[1,1,1\],\[1,0,1\],\[1,1,1\]\]  
> 输出：\[\[1,0,1\],\[0,0,0\],\[1,0,1\]\]**

## 示例 2 ##

![示例2][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`
 *  `-231 <= matrix[i][j] <= 231 - 1`

# 题解 #

## 暴力解法 ##

### 解题思路 ###

先遍历一遍二维数组，将所有等于 `0` 的元素下标存到一个数组中。然后再遍历所有元素等于 `0` 的下标，将相关的行和列的值改为 `0` 即可。时间复杂度为 **O(n3)**。

### 解题代码 ###

class Solution { 
    public:
        void setZeroes(vector<vector<int>>& matrix) { 
            vector<pair<int, int>> m0;
            for (int i = 0; i < matrix.size(); i++) { 
                for (int j = 0; j < matrix[i].size(); j++) { 
                    if (matrix[i][j] == 0) m0.push_back({ i, j});
                }
            }
            for (auto p : m0) { 
                for (int i = 0; i < matrix.size(); i++) { 
                    for (int j = 0; j < matrix[i].size(); j++) { 
                        if (i == p.first || j == p.second) matrix[i][j] = 0;
                    }
                }
            }
        }
    };

## 优化解法（原地算法） ##

### 解题思路 ###

可以直接利用原数组的第 **0** 行和第 **0** 列来标识对应的行和列是否需要全部变为 **0**。这里需要注意的是第 **0** 行和第 **0** 列需要特殊处理，使用两个变量 `r0 = 1` 和 `c0 = 1` 分别标识第 **0** 行和第 **0** 列是否需要变为 **0**。

首先遍历一下第 **0** 行和第 **0** 列如果有一个 **0** 那么说明该行需要变为 **0**，那么就将相应的变量变为 **0**。然后再从第 **1** 行第 **1** 列开始遍历数组，将需要变为 **0** 的行和列的第一个元素变为 **0** 否则就不改变其值。最后再处理第 **0** 行和第 **0** 列。

### 解题代码 ###

class Solution { 
    public:
        void setZeroes(vector<vector<int>>& matrix) { 
            int r0 = 1, c0 = 1; // r0 标识第 0 行是否需要全部变为 0
            // 判断第 0 行是否需要变为 0
            for (int i = 0; i < matrix[0].size(); i++) { 
                if (matrix[0][i] == 0) r0 = 0;
            }
            // 判断第 0 列是否需要变为 0
            for (int i = 0; i < matrix.size(); i++) { 
                if (matrix[i][0] == 0) c0 = 0;
            }
            // 判断其他行和列是否需要变为 0
            for (int i = 1; i < matrix.size(); i++) { 
                for (int j = 1; j < matrix[0].size(); j++) { 
                    if (matrix[i][j] == 0) { 
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                    }
                }
            }
            // 将需要变为 0 的行变为 0
            for (int i = 1; i < matrix.size(); i++) { 
                if (matrix[i][0] == 0) { 
                    for (int j = 0; j < matrix[0].size(); j++) { 
                        matrix[i][j] = 0;
                    }
                }
            }
            // 将需要变为 0 的列变为 0
            for (int i = 1; i < matrix[0].size(); i++) { 
                if (matrix[0][i] == 0) { 
                    for (int j = 0; j < matrix.size(); j++) { 
                        matrix[j][i] = 0;
                    }
                }
            }
            // 最后处理第 0 行和第 0 列
            if (r0 == 0) { 
                for (int i = 0; i < matrix[0].size(); i++) { 
                    matrix[0][i] = 0;
                }
            }
            if (c0 == 0) { 
                for (int i = 0; i < matrix.size(); i++) { 
                    matrix[i][0] = 0;
                }
            }
        }
    };

--------------------

> 未完待续，持续更新中……  
> ![Tomcat我们走][Tomcat]

[Dijkstra]: https://ac-fun.blog.csdn.net/article/details/114548187
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode 73.]: https://leetcode-cn.com/problems/set-matrix-zeroes/
[1]: /images/20221022/54c93ff1c9334ea1923ea9e429ffab6d.png
[2]: https://img-blog.csdnimg.cn/img_convert/9e7fc420a27dad9d8bcdff165e988676.png
[Tomcat]: https://img-blog.csdnimg.cn/20200803154032739.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3,size_16,color_FFFFFF,t_70