Java详解LeetCode 热题 100(18):LeetCode 73. 矩阵置零（Set Matrix Zeroes）详解-EW帮帮网

文章目录

1. 题目描述

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

示例 1:

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

进阶:

一个直观的解决方案是使用 O(mn) 的额外空间，但这不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

2. 理解题目

这道题要求我们在给定的矩阵中，如果发现某个元素为0，就将该元素所在的整行和整列都设置为0。具体来说：

输入是一个 m×n 的二维整数矩阵
我们需要找出所有值为0的元素，并将其所在的行和列全部置为0
要求使用原地算法（即不创建新的矩阵）完成操作
进阶要求是优化空间复杂度，理想情况下只使用常量额外空间

关键点：

不能简单地一边遍历一边置零，因为这样会导致原本不应该置零的元素被错误地置零
需要记录哪些行和列需要被置零
如何高效地记录这些信息，是解题的关键

3. 解法一：使用两个额外数组标记法

3.1 思路

最直观的解法是使用两个额外的数组来记录哪些行和列需要被置为0：

使用一个大小为m的布尔数组row记录哪些行需要置零
使用一个大小为n的布尔数组col记录哪些列需要置零
首先遍历整个矩阵，标记包含0的行和列
然后再次遍历矩阵，根据标记数组将相应的行和列置零

这种方法的空间复杂度为O(m + n)，满足进阶要求中的第二点。

3.2 Java代码实现

class Solution {
    public void setZeroes(int[][] matrix) {
        // 获取矩阵的行数和列数
        int m = matrix.length;
        int n = matrix[0].length;
        
        // 创建两个布尔数组，分别记录哪些行和列需要置零
        boolean[] row = new boolean[m];
        boolean[] col = new boolean[n];
        
        // 第一次遍历：标记需要置零的行和列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        
        // 第二次遍历：根据标记将相应的行和列置零
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

3.3 代码详解

详细解释每一步的意义和实现：

// 获取矩阵的行数和列数
int m = matrix.length;
int n = matrix[0].length;

获取输入矩阵的维度，m表示行数，n表示列数
这是处理二维数组时的常见做法

// 创建两个布尔数组，分别记录哪些行和列需要置零
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];

创建两个布尔类型的数组：
- row数组大小为m，用于标记哪些行需要置零
- col数组大小为n，用于标记哪些列需要置零
布尔数组的默认值为false，表示初始状态下没有行或列需要置零

// 第一次遍历：标记需要置零的行和列
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (matrix[i][j] == 0) {
            row[i] = true;
            col[j] = true;
        }
    }
}

遍历整个矩阵，检查每个元素的值
当发现某个位置(i,j)的元素为0时：
- 将row[i]标记为true，表示第i行需要置零
- 将col[j]标记为true，表示第j列需要置零
这样，第一次遍历结束后，我们就知道了哪些行和列需要被置零

// 第二次遍历：根据标记将相应的行和列置零
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (row[i] || col[j]) {
            matrix[i][j] = 0;
        }
    }
}

再次遍历矩阵，根据row和col数组的标记决定是否将元素置零
如果元素所在的行row[i]或列col[j]被标记为true，则将该元素置为0
这样就完成了原地修改矩阵的操作

3.4 复杂度分析

时间复杂度: O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。需要两次遍历整个矩阵。
空间复杂度: O(m + n)，使用了两个额外的数组来存储需要置零的行和列的信息。

3.5 适用场景

这种解法是解决矩阵置零问题的基础方法，适用于大多数情况。特别是当空间复杂度要求不是特别严格，允许使用O(m + n)额外空间时，这种方法简单直观，容易实现和理解。

4. 解法二：使用矩阵的第一行和第一列作为标记

4.1 思路

为了进一步优化空间复杂度，我们可以利用矩阵的第一行和第一列来记录哪些行和列需要置零，从而避免使用额外的数组：

用两个变量firstRowZero和firstColZero记录第一行和第一列是否原本包含0
使用矩阵的第一行和第一列作为标记数组，记录其余行列是否需要置零
根据标记，将相应的行和列置零
最后，根据firstRowZero和firstColZero的值决定是否将第一行和第一列置零

这种方法的空间复杂度为O(1)，满足进阶要求中的第三点。

4.2 Java代码实现

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        // 记录第一行和第一列是否原本包含0
        boolean firstRowZero = false;
        boolean firstColZero = false;
        
        // 检查第一行是否有0
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }
        
        // 检查第一列是否有0
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }
        
        // 使用第一行和第一列作为标记
        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; // 标记该列需要置零
                }
            }
        }
        
        // 根据第一行和第一列的标记，将对应的行和列置零
        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;
                }
            }
        }
        
        // 如果第一行原本有0，则将第一行全部置零
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        
        // 如果第一列原本有0，则将第一列全部置零
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

4.3 代码详解

详细解释每一步的意义和实现：

// 记录第一行和第一列是否原本包含0
boolean firstRowZero = false;
boolean firstColZero = false;

使用两个布尔变量记录第一行和第一列是否原本包含0
这是必要的，因为我们将使用第一行和第一列来标记其他行列是否需要置零

// 检查第一行是否有0
for (int j = 0; j < n; j++) {
    if (matrix[0][j] == 0) {
        firstRowZero = true;
        break;
    }
}

// 检查第一列是否有0
for (int i = 0; i < m; i++) {
    if (matrix[i][0] == 0) {
        firstColZero = true;
        break;
    }
}

单独检查第一行和第一列是否包含0
如果包含，则相应的标记变量设为true

// 使用第一行和第一列作为标记
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; // 标记该列需要置零
        }
    }
}

从矩阵的第二行和第二列开始遍历（跳过第一行和第一列）
当发现元素matrix[i][j]为0时：
- 将第i行的第一个元素matrix[i][0]置为0，表示第i行需要全部置零
- 将第j列的第一个元素matrix[0][j]置为0，表示第j列需要全部置零

// 根据第一行和第一列的标记，将对应的行和列置零
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;
        }
    }
}

再次遍历矩阵（跳过第一行和第一列）
如果元素所在行的第一个元素为0，或者所在列的第一个元素为0，则将该元素置为0

// 如果第一行原本有0，则将第一行全部置零
if (firstRowZero) {
    for (int j = 0; j < n; j++) {
        matrix[0][j] = 0;
    }
}

// 如果第一列原本有0，则将第一列全部置零
if (firstColZero) {
    for (int i = 0; i < m; i++) {
        matrix[i][0] = 0;
    }
}

最后，根据之前保存的firstRowZero和firstColZero变量的值
决定是否需要将第一行和第一列全部置零

4.4 复杂度分析

时间复杂度: O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。需要进行多次遍历，但总的操作次数与矩阵大小成正比。
空间复杂度: O(1)，只使用了常数额外空间。

4.5 适用场景

这种解法特别适合空间要求严格的场景，它巧妙地利用了矩阵本身的存储空间，避免了使用额外的数组。在面试中，如果被要求优化空间复杂度，这种方法是一个很好的解决方案。

5. 解法三：使用一个标记变量的优化方法

5.1 思路

我们可以进一步优化解法二，只使用一个标记变量：

用一个变量firstColZero记录第一列是否原本包含0
使用矩阵的第一行来标记列是否需要置零，使用第一列来标记行是否需要置零
第一行是否需要置零可以用matrix[0][0]来标记
根据标记，将相应的行和列置零

这种方法同样具有O(1)的空间复杂度，但代码更加简洁。

5.2 Java代码实现

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        // 标记第一列是否原本包含0
        boolean firstColZero = false;
        
        // 第一次遍历，标记需要置零的行和列
        for (int i = 0; i < m; i++) {
            // 检查第一列是否有0
            if (matrix[i][0] == 0) {
                firstColZero = true;
            }
            
            // 从第二列开始遍历，标记第一行和第一列
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0; // 标记该行需要置零
                    matrix[0][j] = 0; // 标记该列需要置零
                }
            }
        }
        
        // 从最后一行和最后一列开始，根据标记置零
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 1; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            
            // 处理第一列
            if (firstColZero) {
                matrix[i][0] = 0;
            }
        }
    }
}

5.3 代码详解

详细解释每一步的意义和实现：

// 标记第一列是否原本包含0
boolean firstColZero = false;

只使用一个布尔变量记录第一列是否原本包含0
第一行是否包含0将通过matrix[0][0]隐式表示

// 第一次遍历，标记需要置零的行和列
for (int i = 0; i < m; i++) {
    // 检查第一列是否有0
    if (matrix[i][0] == 0) {
        firstColZero = true;
    }
    
    // 从第二列开始遍历，标记第一行和第一列
    for (int j = 1; j < n; j++) {
        if (matrix[i][j] == 0) {
            matrix[i][0] = 0; // 标记该行需要置零
            matrix[0][j] = 0; // 标记该列需要置零
        }
    }
}

遍历整个矩阵
记录第一列是否有0
当发现元素matrix[i][j]为0时（从第二列开始）：
- 将第i行的第一个元素置为0
- 将第j列的第一个元素置为0

// 从最后一行和最后一列开始，根据标记置零
for (int i = m - 1; i >= 0; i--) {
    for (int j = n - 1; j >= 1; j--) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
            matrix[i][j] = 0;
        }
    }
    
    // 处理第一列
    if (firstColZero) {
        matrix[i][0] = 0;
    }
}

从矩阵的右下角开始，向左上方向遍历
根据第一行和第一列的标记，将对应的元素置零
最后，根据firstColZero的值决定是否将第一列的元素置零

这种从后向前的遍历顺序是必要的，因为它确保了我们先处理依赖于标记的元素，最后才处理作为标记的第一行和第一列。

5.4 复杂度分析

时间复杂度: O(mn)，与解法二相同。
空间复杂度: O(1)，只使用了一个额外的布尔变量。

5.5 与解法二的比较

解法三和解法二的核心思想相同，都是利用矩阵的第一行和第一列作为标记。主要区别在于：

解法三只使用一个布尔变量，而解法二使用两个
解法三的遍历顺序是从后向前，确保了标记不会被提前修改
解法三代码稍微复杂一些，但效率略高

在实际应用中，这两种解法的性能差异不大，可以根据个人习惯和理解程度选择使用。

6. 详细步骤分析与示例跟踪

让我们通过几个具体的例子，详细跟踪每种解法的执行过程，以加深理解。

6.1 示例1跟踪：基本情况

输入矩阵：

[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]

使用解法一（两个额外数组）跟踪：

初始化：
- m = 3, n = 3
- row = [false, false, false]
- col = [false, false, false]
第一次遍历，标记包含0的行和列：
- 发现matrix[1][1] = 0
- 更新row[1] = true, col[1] = true
- 此时row = [false, true, false], col = [false, true, false]
第二次遍历，根据标记置零：
- 根据row和col数组，将相应位置的元素置为0
- 第1行（row[1]=true）的所有元素置为0
- 第1列（col[1]=true）的所有元素置为0
最终矩阵：
```
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]
```

使用解法二（利用第一行和第一列作为标记）跟踪：

初始化：
- m = 3, n = 3
- firstRowZero = false, firstColZero = false
检查第一行和第一列：
- 第一行没有0，firstRowZero = false
- 第一列没有0，firstColZero = false
使用第一行和第一列标记：
- 发现matrix[1][1] = 0
- 更新matrix[1][0] = 0和matrix[0][1] = 0
此时矩阵状态：
```
[
  [1,0,1],
  [0,0,1],
  [1,1,1]
]
```
根据标记置零：
- 对于matrix[1][1]，因为matrix[1][0] = 0或matrix[0][1] = 0，所以置为0
- 对于matrix[1][2]，因为matrix[1][0] = 0，所以置为0
- 对于matrix[2][1]，因为matrix[0][1] = 0，所以置为0
最终矩阵：
```
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]
```

6.2 示例2跟踪：边界情况

输入矩阵：

[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]

使用解法三（一个标记变量）跟踪：

初始化：
- m = 3, n = 4
- firstColZero = false
第一次遍历：
- 检查第一列，发现matrix[0][0] = 0，设置firstColZero = true
- 标记过程如下：
  - matrix[0][0] = 0（发现matrix[0][0] = 0，无需标记）
  - matrix[0][3] = 0（发现matrix[0][3] = 0，无需标记）
  - matrix[0][0] = 0, matrix[0][3] = 0（已经是0，无需更改）

此时矩阵状态：

[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]

firstColZero = true

从后向前遍历，根据标记置零：
- 根据第一行和第一列的标记，应将第0列和第3列的所有元素置为0
- 逐步更新后的矩阵：
```
[
  [0,1,2,0],
  [0,4,5,0],
  [0,3,1,0]
]
```

最终矩阵：

[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

6.3 示例3跟踪：全零矩阵

输入矩阵：

[
  [0,0],
  [0,0]
]

使用解法一跟踪：

初始化：
- m = 2, n = 2
- row = [false, false]
- col = [false, false]
第一次遍历，标记包含0的行和列：
- 所有元素都是0
- 更新row = [true, true], col = [true, true]
第二次遍历，根据标记置零：
- 所有行和列都需要置零
- 矩阵保持不变
最终矩阵：
```
[
  [0,0],
  [0,0]
]
```

6.4 示例4跟踪：单一元素矩阵

输入矩阵：

[
  [1]
]

使用解法二跟踪：

初始化：
- m = 1, n = 1
- firstRowZero = false, firstColZero = false
检查第一行和第一列：
- 只有一个元素，且不为0
- firstRowZero = false, firstColZero = false
使用第一行和第一列标记：
- 没有元素需要标记
最终矩阵：
```
[
  [1]
]
```

7. 常见错误与优化

7.1 常见错误

直接在遍历过程中修改矩阵：
这是最常见的错误。如果在第一次遍历时就直接将元素所在的行和列置零，会导致后续判断时的错误。

// 错误方法
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (matrix[i][j] == 0) {
            // 直接修改行和列，会影响后续判断
            for (int k = 0; k < n; k++) matrix[i][k] = 0;
            for (int k = 0; k < m; k++) matrix[k][j] = 0;
        }
    }
}

这种方法会导致矩阵中的所有元素最终都被置为0，因为一旦将某行或某列置零，后续遍历到这些位置时，又会将更多的行和列置零。

忘记记录第一行和第一列的状态：
在解法二和解法三中，使用第一行和第一列作为标记。如果忘记先记录它们本身是否包含0，会导致错误的结果。

// 错误方法
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;
        }
    }
}
// 忘记检查第一行和第一列原本是否包含0

标记和置零顺序错误：
在解法三中，如果先处理第一行或第一列，会导致标记信息丢失，影响后续元素的置零操作。

// 错误的处理顺序
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (matrix[i][0] == 0 || matrix[0][j] == 0) {
            matrix[i][j] = 0;
        }
    }
}
// 从前向后处理会破坏标记信息

边界情况处理不当：
忘记处理矩阵为空或只有一行/一列的特殊情况。

// 忘记处理边界情况
public void setZeroes(int[][] matrix) {
    // 没有检查矩阵是否为空
    int m = matrix.length;
    int n = matrix[0].length; // 如果matrix为空，会抛出异常
    // ...
}

7.2 性能优化

提前返回全零矩阵：
如果发现矩阵中的0特别多，可以考虑提前判断是否需要将整个矩阵置零。

// 优化：检查是否需要将整个矩阵置零
boolean allZeroes = true;
for (int i = 0; i < m && allZeroes; i++) {
    for (int j = 0; j < n; j++) {
        if (matrix[i][j] != 0) {
            allZeroes = false;
            break;
        }
    }
}
if (allZeroes) return; // 如果矩阵全是0，无需处理

使用位运算优化空间：
对于行数和列数较小的矩阵，可以使用整数的位来记录哪些行和列需要置零，从而进一步降低空间复杂度。

// 使用位运算记录行列状态（适用于m,n <= 32的情况）
int rowBits = 0;
int colBits = 0;

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (matrix[i][j] == 0) {
            rowBits |= (1 << i); // 设置第i位
            colBits |= (1 << j); // 设置第j位
        }
    }
}

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (((rowBits >> i) & 1) == 1 || ((colBits >> j) & 1) == 1) {
            matrix[i][j] = 0;
        }
    }
}

合并遍历：
对于某些特殊情况，可以尝试合并多次遍历，减少循环次数。

// 标记和处理第一行的同时，记录第一列的状态
boolean firstColZero = false;
for (int i = 0; i < m; i++) {
    if (matrix[i][0] == 0) firstColZero = true;
    for (int j = 1; j < n; j++) {
        // 处理其余部分
    }
}

使用队列记录零元素位置：
另一种思路是使用队列记录所有零元素的位置，然后再次遍历时只处理这些位置的行和列。

Queue<int[]> zeroPositions = new LinkedList<>();
// 记录所有0的位置
for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (matrix[i][j] == 0) {
            zeroPositions.offer(new int[]{i, j});
        }
    }
}

// 处理记录的位置
while (!zeroPositions.isEmpty()) {
    int[] pos = zeroPositions.poll();
    int row = pos[0], col = pos[1];
    // 将该行和该列置零
    for (int j = 0; j < n; j++) matrix[row][j] = 0;
    for (int i = 0; i < m; i++) matrix[i][col] = 0;
}

这种方法适用于矩阵中0很少的情况，但空间复杂度为O(k)，其中k是矩阵中0的数量。

Java详解LeetCode 热题 100(18):LeetCode 73. 矩阵置零（Set Matrix Zeroes）详解

文章目录

1. 题目描述

2. 理解题目

3. 解法一：使用两个额外数组标记法

3.1 思路

3.2 Java代码实现

3.3 代码详解

3.4 复杂度分析

3.5 适用场景

4. 解法二：使用矩阵的第一行和第一列作为标记

4.1 思路

4.2 Java代码实现

4.3 代码详解

4.4 复杂度分析

4.5 适用场景

5. 解法三：使用一个标记变量的优化方法

5.1 思路

5.2 Java代码实现

5.3 代码详解

5.4 复杂度分析

5.5 与解法二的比较

6. 详细步骤分析与示例跟踪

6.1 示例1跟踪：基本情况

6.2 示例2跟踪：边界情况

6.3 示例3跟踪：全零矩阵

6.4 示例4跟踪：单一元素矩阵

7. 常见错误与优化

7.1 常见错误

7.2 性能优化

网站公告

今日签到

热门文章

最新发布