当前位置： 面试刷题>> 矩阵置零(经典算法150题)
### 题目描述
给定一个`m x n`的矩阵，如果一个元素为0，则将其所在行和列的所有元素都置为0。请使用原地算法完成。
**注意**：
1. 你必须使用**原地**算法，也就是说，你只能在原矩阵上进行操作，并且不需要使用额外的空间（除了少数变量）。
2. 矩阵的行数`m`和列数`n`都将通过函数参数给出。
3. 你必须直接修改输入矩阵，而不是返回一个新的矩阵。
### 示例
假设有以下矩阵：
```
[
[1,1,0],
[1,0,1],
[0,1,1]
]
```
运行你的函数后，矩阵应变为：
```
[
[1,0,0],
[0,0,1],
[0,1,0]
]
```
### PHP 示例代码
```php
function setZeroes(&$matrix) {
$m = count($matrix);
if ($m == 0) return;
$n = count($matrix[0]);
$firstRowHasZero = false;
$firstColHasZero = false;
// 第一步：检查第一行和第一列是否有0
for ($i = 0; $i < $m; $i++) {
if ($matrix[$i][0] == 0) {
$firstColHasZero = true;
}
}
for ($j = 0; $j < $n; $j++) {
if ($matrix[0][$j] == 0) {
$firstRowHasZero = true;
}
}
// 第二步：标记需要置为0的行和列
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;
}
}
}
// 第三步：根据标记置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 ($firstRowHasZero) {
for ($j = 0; $j < $n; $j++) {
$matrix[0][$j] = 0;
}
}
if ($firstColHasZero) {
for ($i = 0; $i < $m; $i++) {
$matrix[$i][0] = 0;
}
}
}
// 示例用法
$matrix = [
[1,1,0],
[1,0,1],
[0,1,1]
];
setZeroes($matrix);
print_r($matrix);
```
### Python 示例代码
```python
def setZeroes(matrix):
if not matrix or not matrix[0]:
return
m, n = len(matrix), len(matrix[0])
first_row_has_zero = False
first_col_has_zero = False
# 检查第一行和第一列
for i in range(m):
if matrix[i][0] == 0:
first_col_has_zero = True
for j in range(n):
if matrix[0][j] == 0:
first_row_has_zero = True
# 标记
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# 根据标记置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 first_row_has_zero:
for j in range(n):
matrix[0][j] = 0
if first_col_has_zero:
for i in range(m):
matrix[i][0] = 0
# 示例用法
matrix = [
[1,1,0],
[1,0,1],
[0,1,1]
]
setZeroes(matrix)
print(matrix)
```
### JavaScript 示例代码
```javascript
function setZeroes(matrix) {
if (!matrix.length || !matrix[0].length) return;
const m = matrix.length;
const n = matrix[0].length;
let firstRowHasZero = false;
let firstColHasZero = false;
// 检查第一行和第一列
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) {
firstColHasZero = true;
}
}
for (let j = 0; j < n; j++) {
if (matrix[0][j] === 0) {
firstRowHasZero = true;
}
}
// 标记
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// 根据标记置0
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) {
matrix[i][j] = 0;
}
}
}
// 处理第一行和第一列
if (firstRowHasZero) {
for (let j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (firstColHasZero) {
for (let i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
// 示例用法
const matrix = [
[1,1,0],
[1,0,1],
[0,1,1]
];
setZeroes(matrix);
console.log(matrix);
```
这些示例代码都实现了原地修改矩阵以将所有含0元素的行和列置为0的算法。