力扣经典150题第三十七题：矩阵置零

用户8589624

发布于 2025-11-13 15:58:47

2130

文章被收录于专栏：nginxnginx

力扣经典150题第三十七题：矩阵置零

引言

本篇博客介绍了力扣经典150题中的第三十七题：矩阵置零。题目要求给定一个 m x n 的矩阵，如果矩阵中某个元素为 0 ，则将该元素所在的行和列的所有元素都设为 0，要求使用原地算法实现。

题目详解

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0。要求使用原地算法，即不使用额外的空间。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

解题思路

为了实现不使用额外空间的矩阵置零操作，可以使用原矩阵的第一行和第一列来作为记录标记的空间。

具体步骤如下：

遍历矩阵，如果发现某个元素 matrix[i][j] 为 0，则将对应的第一行和第一列的元素 matrix[i][0] 和 matrix[0][j] 标记为 0。
再次遍历除第一行和第一列之外的矩阵，根据第一行和第一列的标记，将相应位置的元素置为 0。
最后根据第一行和第一列的标记，处理第一行和第一列。

通过上述步骤，可以在原地完成矩阵置零的操作。

代码实现

public class SetMatrixZeroes {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRowZero = false;
        boolean firstColZero = false;

        // Step 1: Mark first row and first column
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }

        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }

        // Step 2: Use first row and first column to mark zero positions
        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;
                }
            }
        }

        // Step 3: Set zeros based on first row and first column marks
        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;
                }
            }
        }

        // Step 4: Handle first row and first column
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }

    public static void main(String[] args) {
        SetMatrixZeroes solution = new SetMatrixZeroes();

        // 示例测试
        int[][] matrix1 = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        System.out.println("输入矩阵1：");
        printMatrix(matrix1);
        solution.setZeroes(matrix1);
        System.out.println("置零后的矩阵1：");
        printMatrix(matrix1);

        int[][] matrix2 = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        System.out.println("输入矩阵2：");
        printMatrix(matrix2);
        solution.setZeroes(matrix2);
        System.out.println("置零后的矩阵2：");
        printMatrix(matrix2);
    }

    private static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
        System.out.println();
    }
}