编写一种算法,若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]
]
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/zero-matrix-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
之前写过一次,这次再写一次。
没有空间复杂度要求的话,顶多只能算是简单题。加上不使用额外的空间,才能算中等题。
具体思路是利用数组的第一行和第一列存储改行或者该列是否需要进行置零操作。
额外使用两个变量来判断第一行或者第一列是否需要进行置零操作。
更多的看注释:
class Solution { public void setZeroes(int[][] matrix) { int len1 = matrix.length; // 题目没有给出数据范围,避免长度为0的坑。 if (len1 == 0) { return; } // 题目没有给出数据范围,避免长度为0的坑。 int len2 = matrix[0].length; if (len2 == 0) { return; } // 判断第一行是否需要置零 boolean lateral = false; // 判断第二行是否需要置零 boolean direct = false; for (int i = 0; i < len1; i ++) { if (matrix[i][0] == 0) { direct = true; break; } } for (int i = 0; i < len2; i ++) { if (matrix[0][i] == 0) { lateral = true; break; } } // 判断某一行和某一列是否需要置零 for (int i = 1; i < len1; i ++) { for (int j = 0; j < len2; j ++) { if (matrix[i][j] == 0) { matrix[0][j] = 0; matrix[i][0] = 0; } } } // 对列进行置零操作 for (int i = 1; i < len2; i ++) { if (matrix[0][i] == 0) { for (int j = 1; j < len1; j ++) { matrix[j][i] = 0; } } } // 对行进行置零操作 for (int i = 1; i < len1; i ++) { if (matrix[i][0] == 0) { for (int j = 1; j < len2; j ++) { matrix[i][j] = 0; } } } // 对第一行进行置零操作 if (lateral) { for (int i = 0; i < len2; i ++) { matrix[0][i] = 0; } } // 对第一列进行置零操作 if (direct) { for (int i = 0; i < len1; i ++) { matrix[i][0] = 0; } } } }