大家好，我就是那个在B站讲算法的「华南溜达虎」。
最近拼多多内部员工爆料说公司内部进行了作息时间调整，从11-11-6改成10-9-6，表面上看工作时长变短了，实际上午休和晚餐时间均缩短为了一个小时，真正的工作时间是一点都没少。而且很多人说9点下班是不可能的，不管你来的多早该几点走还是几点走。
即便是这样，不少人认为拼多多属于愿者上钩，既然选择了去赚钱就不要抱怨，毕竟人家明牌了，给的也确实多。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「矩阵置零」。
题目描述
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
举个例子：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
思路解析
题目要求使用原地算法，顾名思义，就是使用常量的空间复杂度。我们还是先来看下如何使用额外空间来解，再一步步推导常量空间。
使用两个布尔数组rowsZero、colsZero来保存每一行和每一列是否需要置为0，true代表需要置0。假设matrix = [[1,1,1], [1,0,1], [1,1,1]]，两个数组的情况如下图：
进一步观察矩阵的特征，其实我们可以使用矩阵的第一行来代替colsZero数组，矩阵的第一列(除去第一个元素)外加一个额外的变量(表示第0行是否置0)代替rowsZero数组，值为0表示需要置0。过程如下图所示：
这样只需要使用常量的空间复杂度。
C++代码
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int cols = matrix[0].size(), rows = matrix.size();
//保存第一行的状态，1表示第一行不置为0
int zeroRow = 1;
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
if (matrix[row][col] == 0) {
//matrix第0行保存第col列是否置为0
matrix[0][col] = 0;
if (row > 0) {
//matrix第0列保存第row行（除第0行）是否置为0
matrix[row][0] = 0;
} else {
//第0行是否置为0单独保存
zeroRow = 0;
}
}
}
}
for (int row = 1; row < rows; ++row) {
for (int col = 1; col < cols; ++col) {
if (matrix[row][0] == 0 || matrix[0][col] == 0) {
matrix[row][col] = 0;
}
}
}
//第0列置为0
if (matrix[0][0] == 0) {
for (int row = 1; row < rows; ++row) {
matrix[row][0] = 0;
}
}
//第0行置为0
if (zeroRow == 0) {
for (int col = 0; col < cols; ++col) {
matrix[0][col] = 0;
}
}
}
};
python代码
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
rows = len(matrix)
cols = len(matrix[0])
# 保存第一行的状态，1表示第一行不置为0
zero_row = 1
for row in range(rows):
for col in range(cols):
if matrix[row][col] == 0:
# matrix第0行保存第col列是否置为0
matrix[0][col] = 0
if row > 0:
# matrix第0列保存第row行（除第0行）是否置为0
matrix[row][0] = 0
else:
# 第0行是否置为0单独保存
zero_row = 0
for row in range(1, rows):
for col in range(1, cols):
if matrix[row][0] == 0 or matrix[0][col] == 0:
matrix[row][col] = 0
# 第0列置为0
if matrix[0][0] == 0:
for row in range(1, rows):
matrix[row][0] = 0
# 第0行置为0
if zero_row == 0:
for col in range(cols):
matrix[0][col] = 0
复杂度分析
时间复杂度： 需要遍历一遍矩阵所以时间复杂度为O(mn)，其中m是矩阵的行数，n是矩阵的列数。
空间复杂度： O(1)。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
