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

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
• 要求使用原地算法（即不创建新的矩阵）完成操作
• 进阶要求是优化空间复杂度，理想情况下只使用常量额外空间

关键点：

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

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

3.1 思路

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

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

这种方法的空间复杂度为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 思路

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

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

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

4.2 Java代码实现

class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;// 记录第一行和第一列是否原本包含0boolean firstRowZero = false;boolean firstColZero = false;// 检查第一行是否有0for (int j = 0; j < n; j++) {if (matrix[0][j] == 0) {firstRowZero = true;break;}}// 检查第一列是否有0for (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 思路

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

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

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

5.2 Java代码实现

class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;// 标记第一列是否原本包含0boolean firstColZero = false;// 第一次遍历，标记需要置零的行和列for (int i = 0; i < m; i++) {// 检查第一列是否有0if (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++) {// 检查第一列是否有0if (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 与解法二的比较

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

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

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

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

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

6.1 示例1跟踪：基本情况

输入矩阵：

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

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

1. 初始化：

   • m = 3, n = 3
   • row = [false, false, false]
   • col = [false, false, false]

2. 第一次遍历，标记包含0的行和列：

   • 发现matrix[1][1] = 0
   • 更新row[1] = true, col[1] = true
   • 此时row = [false, true, false], col = [false, true, false]

3. 第二次遍历，根据标记置零：

   • 根据row和col数组，将相应位置的元素置为0
   • 第1行（row[1]=true）的所有元素置为0
   • 第1列（col[1]=true）的所有元素置为0

4. 最终矩阵：

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

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

1. 初始化：

   • m = 3, n = 3
   • firstRowZero = false, firstColZero = false

2. 检查第一行和第一列：

   • 第一行没有0，firstRowZero = false
   • 第一列没有0，firstColZero = false

3. 使用第一行和第一列标记：

   • 发现matrix[1][1] = 0
   • 更新matrix[1][0] = 0和matrix[0][1] = 0

4. 此时矩阵状态：

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

5. 根据标记置零：

   • 对于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

6. 最终矩阵：

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

6.2 示例2跟踪：边界情况

输入矩阵：

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

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

1. 初始化：

   • m = 3, n = 4
   • firstColZero = false

2. 第一次遍历：

   • 检查第一列，发现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，无需更改）

3. 此时矩阵状态：

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

   • firstColZero = true

4. 从后向前遍历，根据标记置零：

   • 根据第一行和第一列的标记，应将第0列和第3列的所有元素置为0
   • 逐步更新后的矩阵：

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

5. 最终矩阵：

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

6.3 示例3跟踪：全零矩阵

输入矩阵：

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

使用解法一跟踪：

1. 初始化：

   • m = 2, n = 2
   • row = [false, false]
   • col = [false, false]

2. 第一次遍历，标记包含0的行和列：

   • 所有元素都是0
   • 更新row = [true, true], col = [true, true]

3. 第二次遍历，根据标记置零：

   • 所有行和列都需要置零
   • 矩阵保持不变

4. 最终矩阵：

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

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

输入矩阵：

[[1]
]

使用解法二跟踪：

1. 初始化：

   • m = 1, n = 1
   • firstRowZero = false, firstColZero = false

2. 检查第一行和第一列：

   • 只有一个元素，且不为0
   • firstRowZero = false, firstColZero = false

3. 使用第一行和第一列标记：

   • 没有元素需要标记

4. 最终矩阵：

   [[1]
   ]
   

7. 常见错误与优化

7.1 常见错误

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，因为一旦将某行或某列置零，后续遍历到这些位置时，又会将更多的行和列置零。

2. 忘记记录第一行和第一列的状态：
   在解法二和解法三中，使用第一行和第一列作为标记。如果忘记先记录它们本身是否包含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
   

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

   // 错误的处理顺序
   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;}}
   }
   // 从前向后处理会破坏标记信息
   

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

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

7.2 性能优化

1. 提前返回全零矩阵：
   如果发现矩阵中的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，无需处理
   

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

   // 使用位运算记录行列状态（适用于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;}}
   }
   

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

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

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

   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的数量。