一、题目描述

给定一个 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]]

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

进阶：

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

二、题目分析

1. 问题理解：
   • 给定一个 m x n 的矩阵，如果一个元素为 0，则需要将其所在的行和列的所有元素都设为 0。
   • 要求使用原地算法，即不能使用额外的空间来存储矩阵的副本。
2. 初步思路：
   • 最直观的方法是遍历矩阵，记录哪些行和列需要被置为 0，然后再遍历一次矩阵，将对应的行和列置为 0。
   • 这种方法需要额外的空间来存储行和列的标记，空间复杂度为 O(m + n)。
3. 优化思路：
   • 为了减少空间复杂度，可以利用矩阵的第一行和第一列来标记哪些行和列需要被置为 0。
   • 具体步骤如下：
     1. 首先检查第一行和第一列是否有 0，并用两个布尔变量 r0 和 c0 来记录。
     2. 遍历矩阵的其余部分，如果发现某个元素为 0，则将该元素所在的行和列的第一个元素标记为 0。
     3. 再次遍历矩阵的其余部分，如果某个元素所在的行或列的第一个元素为 0，则将该元素置为 0。
     4. 最后根据 r0 和 c0 的值，决定是否将第一行和第一列全部置为 0。

三、代码实现

package S73;

public class P73 {

	static class Solution {
	    public void setZeroes(int[][] matrix) {
	        int m = matrix.length;
	        int n = matrix[0].length;
	        Boolean r0 = false, c0 = false;
	        for(int i = 0; i < n; i++) {
	        	if(matrix[0][i] == 0) {
	        		r0 = true;
	        		break;
	        	}
	        }
	        
	        for(int i = 0; i < m; i++) {
	        	if(matrix[i][0] == 0) {
	        		c0 = 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;
	        		}
	        	}
	        }
	        
	        if(r0) {
	        	 for (int i = 0; i < m; i++) {
	                 matrix[0][i] = 0;
	             }
	        }
	        
	        if(c0) {
	        	 for (int i = 0; i < n; i++) {
	                 matrix[i][0] = 0;
	             }
	        }
	    }
	}
	
	public static void main(String[] args) {
		int[][] matrix = {{0,1,2,0},{3,4,5,2},{1,3,1,5}};
		int r = matrix.length;
		int c = matrix[0].length;
		Solution solution = new Solution();
		solution.setZeroes(matrix);
		for(int i = 0; i < r; i++) {
			System.out.print("[");
			for(int j = 0; j < c; j++) {
				if(j == 0) System.out.print("[");
				System.out.print(matrix[i][j]);
				if(j < c-1) System.out.print(",");
				if(j == c-1) System.out.print("]");
			}
			if(i < r-1) System.out.print(",");
			if(i == r-1) System.out.print("]");
		}
		
	}
}

输出结果：

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

• 代码中首先检查第一行和第一列是否有 0，并记录在 r0 和 c0 中。
• 然后遍历矩阵的其余部分，将 0 所在的行和列的第一个元素标记为 0。
• 再次遍历矩阵的其余部分，根据标记将对应的元素置为 0。
• 最后根据 r0 和 c0 的值，决定是否将第一行和第一列全部置为 0。

• 时间复杂度：O(m * n)，因为需要遍历整个矩阵两次。
• 空间复杂度：O(1)，只使用了常数个额外空间（r0 和 c0）。

提交结果

四、总结

这一周每天一题矩阵，感觉对于矩阵的熟练度也是在渐渐回归，矩阵需要的注意点：

1. 边界条件

• 矩阵为空：检查矩阵是否为空（matrix == null 或 matrix.length == 0）。
• 矩阵的行和列：明确矩阵的行数（m = matrix.length）和列数（n = matrix[0].length），避免越界访问。
• 单行或单列矩阵：处理只有一行或一列的特殊情况。

2. 遍历方式

• 顺序遍历：通常使用双重循环遍历矩阵，外层循环控制行，内层循环控制列。
• 对角线遍历：某些问题需要按对角线遍历矩阵。(看题解的时候有看到过)
• 螺旋遍历：从外到内按螺旋顺序遍历矩阵。
• BFS/DFS：对于搜索类问题（如岛屿数量、路径搜索），可以使用广度优先搜索（BFS）或深度优先搜索（DFS）。

3. 原地修改

• 是否需要额外空间：如果题目要求原地修改，避免使用额外空间（如复制矩阵）。
• 标记法：利用矩阵本身的空间进行标记（如用特殊值标记需要修改的位置）。
• 覆盖问题：在修改矩阵时，注意是否会覆盖后续需要使用的值。

4. 方向控制

• 方向数组：对于搜索类问题，定义方向数组（如上下左右）来简化代码。
• 边界检查：在移动时，确保新位置在矩阵范围内。

5. 空间复杂度优化

• 利用矩阵本身：如利用第一行和第一列来标记需要修改的行和列。
• 位运算：对于某些问题，可以用位运算压缩状态。

6. 时间复杂度优化

• 避免重复计算：在遍历时，尽量减少重复操作。
• 预处理：提前计算某些值（如前缀和）以减少时间复杂度。
• 二分查找：对于有序矩阵，可以使用二分查找来优化搜索。

7. 常见问题类型

• 搜索问题：
  • 查找特定值（如搜索二维矩阵）。
  • 查找路径（如从左上角到右下角的路径）。
• 修改问题：
  • 将满足条件的行或列置为 0。
  • 旋转矩阵（如顺时针旋转 90 度）。
• 统计问题：
  • 统计岛屿数量。
  • 统计满足条件的子矩阵数量。
• 动态规划：
  • 计算最大正方形或矩形面积。
  • 计算从起点到终点的最小路径和。

8. 代码实现细节

索引计算：注意矩阵的行列索引从 0 开始，避免越界。

• 特殊值处理：如用 -1 或 Integer.MIN_VALUE 标记已访问的位置。
• 循环终止条件：确保循环不会无限执行。