iven a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
//如果某个元素为0,则把该元素所在的行和列都设为0。本题用了o(1)的space
//先看第一行第一列是不是有0,用fr,fc记录。扫描剩下的元素,如果遇到0,就把对应的第一行第一列元素赋值为0,如matrix[2,3]为0,就把matrix[2,0]和matrix[0,3]设为0。
//从1,1开始扫描,如果元素对应的第一行或第一列元素为0,则把它也设为0
//处理第一行和第一列
class Solution {
public void setZeroes(int[][] matrix) {
boolean fr = false;
boolean 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 j = 0; j < matrix.length; j++) {
matrix[j][0] = 0;
}
}
}
}
原文地址:http://www.cnblogs.com/MarkLeeBYR/p/16886782.html