题目描述

给定一个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 示例代码

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 示例代码

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 示例代码

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的算法。