力扣经典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(); } }
示例演示
展示了两个不同的矩阵输入，并输出了矩阵置零后的结果。
复杂度分析
该解法的时间复杂度为 O(m * n)，空间复杂度为 O(1)，满足题目要求的原地修改条件。
总结
本篇博客介绍了如何使用原地算法实现矩阵置零
操作，通过标记矩阵的第一行和第一列来记录零元素的位置，然后根据标记将相应位置置为 0，最终完成了矩阵置零的操作。
