题目描述
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 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]
]
进阶:
- 一个直接的解决方案是使用 O(m**n) 的额外空间，但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
- 你能想出一个常数空间的解决方案吗？
常规方法
思路
- 扫描整个矩阵，把为 0 的元素的坐标记录下来，全部存为一个动态数组
- 对动态数组中的每一个坐标值，把对应的整行和整列置为 0
这样处理的速度较慢，因为可能会出现重复处理的情况。
源代码
public void setZeroes (int[][] matrix) {
List<List<Integer>> flag = new ArrayList<List<Integer>>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 0) {
flag.add(Arrays.asList(i,j));
}
}
}
for (List<Integer> integers : flag) {
int row = integers.get(0);
int col = integers.get(1);
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
for (int j = 0; j < matrix[i].length; j++) {
matrix[row][j] = 0;
}
}
}
}
方法二：常数空间解决方案
思路也比较类似，找到一个为 0 的元素，记录它的横纵坐标，再把相应的行列置零。需要注意的是，当原始矩阵中的 0 元素在第一行或者第一列时，需要用两个辅助变量记录下来，特殊处理一下。
源代码
public void setZeroes(int[][] matrix) {
boolean fr = false,fc = false;
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
if(matrix[i][j] == 0) {
if(i == 0) fr = true;
if(j == 0) fc = true;
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for(int i = 1; i < matrix.length; i++) {
for(int j = 1; j < matrix[0].length; j++) {
if(matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if(fr) {
for(int j = 0; j < matrix[0].length; j++) {
matrix[0][j] = 0;
}
}
if(fc) {
for(int i = 0; i < matrix.length; i++) {
matrix[i][0] = 0;
}
}
}