矩阵置零

题目要求

给定一个 m 行 n 列的矩阵，要求编写一个算法，当矩阵中的某个元素值为 0 时，将该元素所在的整行和整列的所有元素都设置为 0。这个过程需要在原矩阵上直接进行，即不允许使用额外的存储空间来创建矩阵的副本。

解题思路

由于题目要求不能使用额外的存储空间，我们不能直接创建一个同样大小的矩阵来标记 0 元素的位置。因此，我们需要在原矩阵上进行标记，以便知道哪些行和列需要被设置为 0。

1. 首先遍历矩阵，我们可以使用矩阵的第一行和第一列来记录该行或该列是否需要被设置为 0。但在此之前，我们需要两个标记变量来分别记录第一行和第一列是否原本就包含 0（因为第一行和第一列也是矩阵的一部分，它们也可能需要被设置为 0）。

2. 设置标记变量：通过遍历第一行和第一列，如果发现有 0，则将对应的标记变量设置为 true。

3. 使用第一行和第一列记录其他行列是否包含 0：从第二行第二列开始遍历矩阵中的每个元素，如果遇到 0，则将该元素所在行的第一个元素和所在列的第一个元素设置为 0。这样做的目的是使用矩阵的边缘作为标记，来记录哪些行列需要被置 0。

4. 根据第一行和第一列的标记来更新矩阵：再次遍历矩阵，这次是从第二行第二列开始，如果发现某行的第一个元素或某列的第一个元素为 0，则将当前遍历到的元素设置为 0。

5. 根据标记变量更新第一行和第一列：最后，根据第一行和第一列的标记变量，如果它们是 true，则将整行或整列的元素设置为 0。

这样，我们就可以在不使用额外空间的情况下，将矩阵中的相应行列元素设置为 0。注意，在实际编码时，要小心处理第一行和第一列的标记，以免它们被提前更新导致信息丢失。

Golang 版本

package main

import "fmt"

func setZeroes(matrix [][]int) {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return
    }

    m, n := len(matrix), len(matrix[0])
    firstRowHasZero := false
    firstColHasZero := false

    // Check if the first row has a zero
    for j := 0; j < n; j++ {
        if matrix[0][j] == 0 {
            firstRowHasZero = true
            break
        }
    }

    // Check if the first column has a zero
    for i := 0; i < m; i++ {
        if matrix[i][0] == 0 {
            firstColHasZero = true
            break
        }
    }

    // Use first row and column as markers, set matrix[i][0] and matrix[0][j] to 0 if matrix[i][j] is 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
            }
        }
    }

    // Zero out cells based on the markers in the first row and column
    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
            }
        }
    }

    // Zero out the first row if needed
    if firstRowHasZero {
        for j := 0; j < n; j++ {
            matrix[0][j] = 0
        }
    }

    // Zero out the first column if needed
    if firstColHasZero {
        for i := 0; i < m; i++ {
            matrix[i][0] = 0
        }
    }
}

func main() {
    matrix := [][]int{
        {1, 1, 1},
        {1, 0, 1},
        {1, 1, 1},
    }
    setZeroes(matrix)
    fmt.Println(matrix)
}

这段代码实现了上述的解题思路。首先，它检查第一行和第一列是否包含 0，然后使用第一行和第一列作为标记，遍历剩余的矩阵元素，根据标记将需要置 0 的行和列元素更新。最后，根据第一行和第一列的标记变量，更新第一行和第一列本身。

C++版本

#include <vector>
#include <iostream>

void setZeroes(std::vector<std::vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    bool firstRowHasZero = false;
    bool firstColHasZero = false;

    // Check if the first row has a zero
    for (int j = 0; j < n; ++j) {
        if (matrix[0][j] == 0) {
            firstRowHasZero = true;
            break;
        }
    }

    // Check if the first column has a zero
    for (int i = 0; i < m; ++i) {
        if (matrix[i][0] == 0) {
            firstColHasZero = true;
            break;
        }
    }

    // Use first row and column as markers
    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            if (matrix[i][j] == 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // Zero out cells based on the markers in the first row and column
    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;
            }
        }
    }

    // Zero out the first row if needed
    if (firstRowHasZero) {
        for (int j = 0; j < n; ++j) {
            matrix[0][j] = 0;
        }
    }

    // Zero out the first column if needed
    if (firstColHasZero) {
        for (int i = 0; i < m; ++i) {
            matrix[i][0] = 0;
        }
    }
}

int main() {
    std::vector<std::vector<int>> matrix = {
        {0, 1, 2, 0},
        {3, 4, 5, 2},
        {1, 3, 1, 5}
    };

    setZeroes(matrix);

    for (const auto& row : matrix) {
        for (int val : row) {
            std::cout << val << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

这段 C++代码实现了与 Golang 版本相同的逻辑。首先检查第一行和第一列是否包含 0，然后使用第一行和第一列作为标记，遍历剩余的矩阵元素，根据标记将需要置 0 的行和列元素更新。最后，根据第一行和第一列的标记变量，更新第一行和第一列本身。

Python 版本

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    firstRowHasZero = not all(matrix[0][j] != 0 for j in range(n))
    firstColHasZero = not all(matrix[i][0] != 0 for i in range(m))

    # Use first row and column as markers
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[0][j] = 0
                matrix[i][0] = 0

    # Zero out cells based on the markers in the first row and column
    for i in range(1, m):
        for j in range(1, n):
            if matrix[0][j] == 0 or matrix[i][0] == 0:
                matrix[i][j] = 0

    # Zero out the first row if needed
    if firstRowHasZero:
        for j in range(n):
            matrix[0][j] = 0

    # Zero out the first column if needed
    if firstColHasZero:
        for i in range(m):
            matrix[i][0] = 0

# Example usage:
matrix = [
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]
setZeroes(matrix)
for row in matrix:
    print(row)

这段 Python 代码实现了矩阵置零的功能。首先检查第一行和第一列是否包含 0，然后使用第一行和第一列作为标记，遍历剩余的矩阵元素，根据标记将需要置 0 的行和列元素更新。最后，根据第一行和第一列的标记变量，更新第一行和第一列本身。

Java 版本

public class Solution {
    public void setZeroes(int[][] matrix) {
        boolean firstRowHasZero = false;
        boolean firstColumnHasZero = false;
        int rows = matrix.length;
        int columns = matrix[0].length;

        // Check if the first row has any zeros
        for (int j = 0; j < columns; j++) {
            if (matrix[0][j] == 0) {
                firstRowHasZero = true;
                break;
            }
        }

        // Check if the first column has any zeros
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == 0) {
                firstColumnHasZero = true;
                break;
            }
        }

        // Use first row and column as markers, set the markers
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Use the markers to set elements to zero
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Set first row to zero if needed
        if (firstRowHasZero) {
            for (int j = 0; j < columns; j++) {
                matrix[0][j] = 0;
            }
        }

        // Set first column to zero if needed
        if (firstColumnHasZero) {
            for (int i = 0; i < rows; i++) {
                matrix[i][0] = 0;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] matrix = {
            {1, 1, 1},
            {1, 0, 1},
            {1, 1, 1}
        };
        solution.setZeroes(matrix);
        for (int[] row : matrix) {
            for (int val : row) {
                System.out.print(val + " ");
            }
            System.out.println();
        }
    }
}

这段 Java 代码实现了矩阵置零的功能。首先检查第一行和第一列是否包含 0，然后使用第一行和第一列作为标记，遍历剩余的矩阵元素，根据标记将需要置 0 的行和列元素更新。最后，根据第一行和第一列的标记变量，更新第一行和第一列本身。

Rust 版本

fn set_zeroes(matrix: &mut Vec<Vec<i32>>) {
    let mut first_row_has_zero = false;
    let mut first_col_has_zero = false;
    let rows = matrix.len();
    let cols = matrix[0].len();

    // Check if the first row has any zeros
    for j in 0..cols {
        if matrix[0][j] == 0 {
            first_row_has_zero = true;
            break;
        }
    }

    // Check if the first column has any zeros
    for i in 0..rows {
        if matrix[i][0] == 0 {
            first_col_has_zero = true;
            break;
        }
    }

    // Use first row and column as markers, set the markers
    for i in 1..rows {
        for j in 1..cols {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // Use the markers to set elements to zero
    for i in 1..rows {
        for j in 1..cols {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0;
            }
        }
    }

    // Set first row to zero if needed
    if first_row_has_zero {
        for j in 0..cols {
            matrix[0][j] = 0;
        }
    }

    // Set first column to zero if needed
    if first_col_has_zero {
        for i in 0..rows {
            matrix[i][0] = 0;
        }
    }
}

fn main() {
    let mut matrix = vec![
        vec![1, 1, 1],
        vec![1, 0, 1],
        vec![1, 1, 1],
    ];
    set_zeroes(&mut matrix);
    for row in matrix {
        println!("{:?}", row);
    }
}

这段 Rust 代码实现了矩阵置零的功能。首先检查第一行和第一列是否包含 0，然后使用第一行和第一列作为标记，遍历剩余的矩阵元素，根据标记将需要置 0 的行和列元素更新。最后，根据第一行和第一列的标记变量，更新第一行和第一列本身。在main函数中，我们创建了一个示例矩阵，调用set_zeroes函数，并打印出修改后的矩阵。

总结

上面的 Rust 代码解决了矩阵置零的问题，其核心思想是使用矩阵的第一行和第一列作为标记数组，以此来记录哪些行和列需要被置零。这样做的好处是不需要额外的存储空间。具体步骤如下：

1. 首先遍历第一行和第一列，检查它们是否包含 0，这是因为后续的算法会改变第一行和第一列的值，所以需要先记录下它们原本是否应该被置零。

2. 从第二行和第二列开始遍历矩阵的其余部分，如果发现一个元素的值为 0，则将其所在行的第一个元素和所在列的第一个元素设置为 0。这样做是为了使用矩阵的第一行和第一列来标记该行和该列是否需要被置零。

3. 再次遍历矩阵（除了第一行和第一列），这次是根据第一行和第一列的标记来更新矩阵。如果某个元素所在的行的第一个元素或所在的列的第一个元素被设置为 0，则将该元素也设置为 0。

4. 最后，根据第一步中记录的信息，决定是否需要将第一行和第一列置零。

这种方法的关键在于，它避免了使用额外的存储空间，而是巧妙地利用了矩阵本身的空间来存储信息。这对于空间复杂度要求高的场景非常有用。