我要评论csdn话题挑战赛第2期
参赛话题：算法题解
往期打卡回顾总结：
题目链接与描述
编写一种算法，若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]
]
关键词： 标记数组
这道题，标注是中等题。
- 首先考虑存储原始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;
}
}
方法二：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 的空间复杂度；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;
}
}
}
结尾
欢迎评论区交流，每日打卡，冲冲冲！！！
发表评论