用首行/首列充当标记位，先记录首行首列是否含零，再标记并回填，O(1) 额外空间。
OJ: leetcodecn
题目 ID: set-matrix-zeroes
难度:普及+/提高
标签:数组矩阵cpppython
日期: 2026-07-28 22:05
题意
m×n 矩阵，如果某元素为 0，将其所在行和列全部置零。原地修改。
思路
用额外行列集合记录零位置 O(m+n) 空间。O(1) 空间优化：用矩阵首行首列作为标记位，先单独记录首行首列本身是否含零，再用首行首列标记其他行列是否有零，最后回填。
代码
cpp
/**
* Author by Rainboy
*/
// main.cpp：用首行/首列充当标记，O(1) 额外空间。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void setZeroes(vector<vector<int>> &matrix) {
int m = matrix.size(), n = matrix[0].size();
bool row0 = false, col0 = false;
for (int j = 0; j < n; j++)
if (matrix[0][j] == 0)
row0 = true;
for (int i = 0; i < m; i++)
if (matrix[i][0] == 0)
col0 = true;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
if (matrix[i][j] == 0)
matrix[i][0] = matrix[0][j] = 0;
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
if (matrix[i][0] == 0 || matrix[0][j] == 0)
matrix[i][j] = 0;
if (row0)
for (int j = 0; j < n; j++)
matrix[0][j] = 0;
if (col0)
for (int i = 0; i < m; i++)
matrix[i][0] = 0;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m, n;
cin >> m >> n;
vector<vector<int>> a(m, vector<int>(n));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
Solution().setZeroes(a);
for (auto &row : a) {
for (int x : row)
cout << x << ' ';
cout << '\n';
}
return 0;
}python
#!/usr/bin/env python3
from typing import List
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
row0 = any(matrix[0][j] == 0 for j in range(n))
col0 = any(matrix[i][0] == 0 for i in range(m))
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if row0:
for j in range(n):
matrix[0][j] = 0
if col0:
for i in range(m):
matrix[i][0] = 0
def main() -> None:
m, n = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
Solution().setZeroes(a)
for row in a:
print(*row)
if __name__ == "__main__":
main()复杂度
- 时间复杂度：O(mn)，遍历矩阵两次。
- 空间复杂度：O(1)。
总结
"借用已有空间作标记"是原地算法的常见技巧，关键在于防止标记本身被提前覆盖。