LeetCode 73. 矩阵置零 空间优化题解，一题体会时间换空间、不使用额外空间。

题目

73. 矩阵置零

https://leetcode.cn/problems/set-matrix-zeroes/

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

你能想出一个仅使用常量空间的解决方案吗？

逐行逐列标记0状态

思路

每行每列开辟一个数组，记录该行该列是否有0。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
    * 粗暴：存零所在位置
    */
public static int[][] setZeroesBruteForce(int[][] matrix) {
    boolean[] zeroRows = new boolean[matrix.length];
    boolean[] zeroColumns = new boolean[matrix[0].length];
    for (int row = 0; row < matrix.length; row++) {
        for (int column = 0; column < matrix[row].length; column++) {
            if (matrix[row][column] == 0) {
                zeroRows[row] = true;
                zeroColumns[column] = true;
            }
        }
    }

    for (int row = 0; row < matrix.length; row++) {
        for (int column = 0; column < matrix[row].length; column++) {
            if (zeroRows[row] || zeroColumns[column]) {
                matrix[row][column] = 0;
            }
        }
    }
    return matrix;
}

复杂度分析

时间

遍历了两次矩阵，时间复杂度O(mn)。

空间

使用了额外的两个数组，一个行数大小，一个列数大小，空间复杂度大致为O(m+n)。

使用首行首列标记0状态

思路

题干中希望我们使用O(1)的空间，不开辟额外空间即为O(1)。同时，一般时间换空间即可提升空间性能。

我们使用首行首列记录每行每列0的状态。

对于首行首列原本0的状态，我们预先遍历一次判断，后面统一处理。

这里时间复杂度提升到了O(mn+m+n)，由于大O算法忽略低阶，因此视为与解法1一致。

这道题很适合用来理解时间换空间、不使用额外空间。

代码

 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

/**
    * 取巧解：
    * 1. 使用0行0列记录行列0值情况，不额外申请空间
    * 2. 同时提前判断0行0列原本0值的情况，使用boolean标记，最后刷新0行0列
    * <p>
    * 执行用时：
    * 0 ms
    * , 在所有 Java 提交中击败了
    * 100.00%
    * 的用户
    * 内存消耗：
    * 42.8 MB
    * , 在所有 Java 提交中击败了
    * 67.48%
    * 的用户
    * 通过测试用例：
    * 164 / 164
    */
public int[][] setZeroesZeroRowCol(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;

    // 使用第一列记录该行是否需要置为0，本身某行出现了0值时，matrix[row][0]就应该==0
    // 一行一列是否有0
    boolean row0Zero = false;
    boolean col0Zero = false;
    for (int row = 0; row < m; row++) {
        if (matrix[row][0] == 0) {
            col0Zero = true;
            break;
        }
    }
    for (int col = 0; col < n; col++) {
        if (matrix[0][col] == 0) {
            row0Zero = true;
            break;
        }
    }

    // 判断 是否有0
    for (int row = 1; row < m; row++) {
        for (int col = 1; col < n; col++) {
            if (matrix[row][col] == 0) {
                matrix[row][0] = 0;
                matrix[0][col] = 0;
            }
        }
    }
    // 将 第二行第二列开始 置0
    for (int row = 1; row < m; row++) {
        for (int col = 1; col < n; col++) {
            if (matrix[row][0] == 0 || matrix[0][col] == 0) {
                matrix[row][col] = 0;
            }
        }
    }
    // 处理第一行第一列
    if (col0Zero) {
        for (int row = 0; row < m; row++) {
            matrix[row][0] = 0;
        }
    }
    if (row0Zero) {
        for (int col = 0; col < n; col++) {
            matrix[0][col] = 0;
        }
    }
    return matrix;
}

复杂度分析

时间

时间复杂度提升到了O(mn+m+n)，由于大O算法忽略低阶，为O(mn)。

空间

未使用额外空间，复杂度O(1)。