Set Matrix Zero
给定一个m×n矩阵,如果一个元素是0,则将其所在行和列全部元素变成0。
需要在原地完成。
样例
给出一个矩阵[[1,2],[0,3]],返回[[0,2],[0,0]]
挑战
你是否使用了额外的空间?
一个直接的解决方案是使用O(MN)的额外空间,但这并不是一个好的方案。
一个简单的改进方案是使用O(M + N)的额外空间,但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗?
Solution
- 设置两个布尔型标示符flagrow,flagcol用来保存第0行和第0列是否需要置0,初始值false
- 遍历第0行,如果遇到0,则将flag_row=true
- 同上遍历第0列,如果遇到0,则将flag_col=true
- 遍历剩下的元素即i从1开始,j从一开始,如果遇到某个元素【i,j】为0,则将matrix[i][0]=0,matrix[0][j]=0
- 遍历第0行,遇到matrix[0][j]=0则设置此列上的所有元素为0
- 遍历第0列,遇到matrix[i][0]=0则设置此行上的所有元素为0
- 判断flag_row是否为true,是的话设置第0行元素均为0
- 判断flag_col是否为true,是的话设置第0列元素均为0
- 至此,题目完成
Complexity
时间复杂度 O(n2 ),空间复杂度 O(n)
Code
public class Solution {
/**
* @param matrix: A list of lists of integers
* @return: Void
*/
public void setZeroes(int[][] matrix) {
int row = matrix.length;
if (row == 0) {
return;
}
int col = matrix[0].length;
int rowIndex = 0;
int colIndex = 0;
boolean stop = false;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 0) {
rowIndex = i;
colIndex = j;
stop = true;
break;
}
}
if (stop) {
break;
}
}
if (!stop) {
return;
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == rowIndex || j == colIndex) {
continue;
}
if (matrix[i][j] == 0) {
matrix[rowIndex][j] = 0;
matrix[i][colIndex] = 0;
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == rowIndex || j == colIndex) {
continue;
}
if (matrix[rowIndex][j] == 0 || matrix[i][colIndex] == 0) {
matrix[i][j] = 0;
}
}
}
for (int i = 0; i < row; i++) {
matrix[i][colIndex] = 0;
}
for (int j = 0; j < col; j++) {
matrix[rowIndex][j] = 0;
}
}
}