大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位同学，秋招拿了17个offer，市面上大中厂的offer基本都拿完了，字节、腾讯、阿里、百度、美团、京东、快手给的年包基本都是40w以上，拼多多给了68w+，一下子超预期太多，有点犹豫要不要去。楼主是top3本硕，一开始投的算法被虐惨了，然后转投开发，结果一顿乱杀成了offer收割机。
评论区大多数同学认为拼多多性价比不高，工时太长，还有竞业协议，而且楼主还是女生没必要去拼多多卷。还有同学开玩笑说，跟你们计算机专业的拼了。
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们来分享一道拼多多的面试原题「矩阵置零」。
题目描述
给定一个 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 ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
