[坚持打卡23天]力扣leetcode 面试题 01.08. 零矩阵

CSDN话题挑战赛第2期
参赛话题：算法题解

往期打卡回顾总结：

• 第一天的图的节点通路dfs、bfs，顺便复习一下图的相关概念
• 第二天的模拟题，重新排列单词间的空格
• 第三天快慢指针，重新分组数字
• 第四天也是归纳题，优美队列
• 第五天，动态规划，最长定差数列
• 第六天，修建二叉树，回顾树的遍历
• 第七天，打工人，k人最低成本题
• 第八天，二分查找，数组特征值
• 第九天，贪心算法，最大交换
• 第十一天，真值表，找规律，灯泡开关
• 第十二天，第一次接触扫描线，覆盖面积
• 第十三天，滑动窗口，hash表，相同字符间最长字串
• 第十五天，矩阵,hash表，人工岛
• 第十六天，剪枝，递归，求k个相等子集
• 第十八天，也是hash表，是否能连成数组
• 第二十天，三种方式、异或、求和、原地hash，求消失两位数
• 第二十一天，hash表、重排序，字符重排
• 第二十二天，字符匹配，字符串轮转

题目链接与描述

编写一种算法，若M × N矩阵中某个元素为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]
]

关键词： 标记数组

这道题，标注是中等题。

1. 首先考虑存储原始0值位置后，将横纵置0即可

方法一：标记数组 m n

运行截图

代码

	public void setZeroes(int[][] matrix) {
		boolean[][] zero = new boolean[matrix.length][matrix[0].length];
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				zero[i][j] = matrix[i][j] == 0;
			}
		}
		for (int i = zero.length - 1; i >= 0; i--) {
			for (int j = zero[i].length - 1; j >= 0; j--) {
				if (zero[i][j]) {
					setZeroesXY(matrix, i, j);
				}
			}
		}
	}

	private void setZeroesXY(int[][] matrix, int i, int j) {
		for (int i1 = matrix.length - 1; i1 >= 0; i1--) {
			matrix[i1][j] = 0;
		}
		for (int j1 = matrix[i].length - 1; j1 >= 0; j1--) {
			matrix[i][j1] = 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
25
26
27

方法二：m + n 的复杂度

和稀疏图一样，我们使用m x n 的矩阵很多空间是浪费掉了，我们只需要一行或者一列即可，同时遍历的时候也只需要满足在行列上有0即可

运行截图

代码

public void setZeroes(int[][] matrix) {
		boolean[] row = new boolean[matrix.length];
		boolean[] col = new boolean[matrix[0].length];
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				if (matrix[i][j] == 0) {
					row[i] = col[j] = true;
				}
			}
		}
		for (int i = matrix.length - 1; i >= 0; i--) {
			for (int j = matrix[i].length - 1; j >= 0; j--) {
				if (col[j] || row[i]) {
					matrix[i][j] = 0;
				}
			}
		}
	}


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

方法三： 1 的空间复杂度；mn的时间复杂度

开始看题解了，第一遍还没懂，中等难度也可能是在这里，实现出来简单，要求对应时间空间复杂度的难想；

思路就是利用行列都会消掉，把矩阵的0位用来存储是否消除，节省了m+n的空间，但是需要注意如果开始0位上有0，那么需要额外处理对应行列；

运行截图

代码

	public void setZeroes(int[][] matrix) {
		int n = matrix.length, m = matrix[0].length;
		// 起始0位是否有0
		boolean row0 = false;
		boolean col0 = false;
		for (int i = 0; i < n; i++) {
			if (matrix[i][0] == 0) {
				col0 = true;
				break;
			}
		}
		for (int j = 0; j < m; j++) {
			if (matrix[0][j] == 0) {
				row0 = true;
				break;
			}
		}
		// 从1位开始,归拢到0位
		for (int i = 1; i < n; i++) {
			for (int j = 1; j < m; j++) {
				if (matrix[i][j] == 0) {
					matrix[0][j] = matrix[i][0] = 0;
				}
			}
		}
		// 开始遍历1判断是否需要消除
		for (int i = 1; i < n; i++) {
			for (int j = 1; j < m; j++) {
				if (matrix[0][j] == 0 || matrix[i][0] == 0) {
					matrix[i][j] = 0;
				}
			}
		}
		if (col0) {
			for (int i = 0; i < n; i++) {
				matrix[i][0] = 0;
			}
		}

		if (row0) {
			for (int i = 0; i < m; i++) {
				matrix[0][i] = 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

结尾

欢迎评论区交流，每日打卡，冲冲冲！！！