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

力扣经典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]]

解题思路

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

具体步骤如下：

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

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

代码实现

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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

示例演示

展示了两个不同的矩阵输入，并输出了矩阵置零后的结果。

复杂度分析

该解法的时间复杂度为 O(m * n)，空间复杂度为 O(1)，满足题目要求的原地修改条件。

总结

本篇博客介绍了如何使用原地算法实现矩阵置零

操作，通过标记矩阵的第一行和第一列来记录零元素的位置，然后根据标记将相应位置置为 0，最终完成了矩阵置零的操作。