🚀 力扣热题 73：矩阵置零（详解 + 多种解法）
📌 题目描述
给定一个
m x n的整数矩阵matrix，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请你 原地 使用常量空间解决。
🎯 示例
输入：
matrix = [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1]
]
输出：
[
[1, 0, 1],
[0, 0, 0],
[1, 0, 1]
]
💡 解题思路一：额外标记数组
🔍 思路
- 创建两个额外的数组
row[]和col[]分别标记哪些行和哪些列需要被置为 0； - 遍历一遍矩阵，标记所有包含 0 的行和列；
- 再次遍历矩阵，根据标记将对应的行和列设为 0。
✅ Go 实现
func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
row := make([]bool, m)
col := make([]bool, n)
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if matrix[i][j] == 0 {
row[i] = true
col[j] = true
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if row[i] || col[j] {
matrix[i][j] = 0
}
}
}
}
📊 复杂度分析
| 时间复杂度 | 空间复杂度 |
|---|---|
| O(m * n) | O(m + n) |
💡 解题思路二：使用矩阵第一行和第一列作为标记（原地操作）
🔍 思路
为了节省空间，我们可以利用矩阵的第一行和第一列来标记需要置 0 的行和列。
步骤如下：
- 用两个变量记录第一行和第一列是否需要置零；
- 使用剩下的矩阵作为标记区域；
- 倒序更新矩阵，防止污染标记。
✅ Go 实现
func setZeroes(matrix [][]int) {
m, n := len(matrix), len(matrix[0])
firstRowZero := false
firstColZero := false
for i := 0; i < m; i++ {
if matrix[i][0] == 0 {
firstColZero = true
}
}
for j := 0; j < n; j++ {
if matrix[0][j] == 0 {
firstRowZero = true
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][j] == 0 {
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
if firstRowZero {
for j := 0; j < n; j++ {
matrix[0][j] = 0
}
}
if firstColZero {
for i := 0; i < m; i++ {
matrix[i][0] = 0
}
}
}
📊 复杂度分析
| 时间复杂度 | 空间复杂度 |
|---|---|
| O(m * n) | O(1) |
🧠 注意事项
- 原地操作 时要避免一开始就修改标记信息，顺序非常关键；
- 可以从矩阵尾部开始遍历，防止影响标记；
- 考察空间压缩技巧，理解“用已有空间做标记”的思路。
✅ 总结
| 解法 | 是否原地操作 | 额外空间 | 思维难度 |
|---|---|---|---|
| 标记数组 | ❌ 否 | O(m+n) | ⭐️⭐️ |
| 原地标记 | ✅ 是 | O(1) | ⭐️⭐️⭐️⭐️ |
📌 推荐练习
- 🔁 289. 生命游戏（原地标记问题）
- 📦 54. 螺旋矩阵（二维数组遍历）
- 🎯 面试经典题型，考察空间优化和矩阵操作能力
💡 如果觉得这篇文章对你有帮助，欢迎点赞 👍、收藏 ⭐、评论 💬、关注 💻！我会持续更新高质量 LeetCode 热题解析。一起刷题，一起进步！🚀🎯
