程序员面试金典-1.8 零矩阵。编写一种算法，若 M ×N 矩阵中某个元素为 0，则将其所在的行与列清零。

解法一：

思想：计下每一个0元素的行列，放在集合中，然后集合转数组，（直接放数组也行，感觉自己有点多余，原本想减少数组实例的内存，但是也增加了对象。得不偿失吧，两者的空间复制度都是一样）；然后更具对应的数组的行列，将其变为0

public class SetZeroTest {
public static void main(String[] args) {
int[][] matrix = {{1, 2, 3, 4}, {5, 0, 7, 8}, {9, 10, 11, 12, 0}, {13, 14, 15, 16, 5}};

System.out.println("修改前数组：");
for (int i = 0; i < matrix.length; i++) {
System.out.println(Arrays.toString(matrix[i]));
        }
setZero(matrix);
System.out.println("修改后数组：");
for (int i = 0; i < matrix.length; i++) {
System.out.println(Arrays.toString(matrix[i]));
        }
    }

static void setZero(int[][] matrix) {
Set<Integer> rows = new HashSet<>();
Set<Integer> columns = new HashSet<>();
// 把每一个0元素的行列索引保存起来
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 0) {
rows.add(i);
columns.add(j);
                }
            }
        }

Object[] rowsArray =  rows.toArray();
Object[] columnsArray = columns.toArray();

int temp;
// 把rows中对应的行都设置成空行
for (int i = 0; i < rowsArray.length; i++) {
temp = (int)rowsArray[i];
for (int j = 0; j < matrix[temp].length; j++) {
matrix[(int)rowsArray[i]][j] = 0;
            }
        }
// 把columns中对应的行都设置成空列
for (int i = 0; i < columnsArray.length; i++) {
for (int j = 0; j < matrix.length; j++) {
temp = (int)columnsArray[i];
System.out.println(j + "temp = " + temp);
if (matrix[j].length - 1 < temp ) {
continue;
                }
matrix[j][temp] = 0;
            }

        }
    }
}
      

通过书籍学习到的进阶方法：

思想：为了提高空间利用率，可以选用位向量替代布尔数组。存储空间的复杂度仍然为 O(N)。通过使用第一行替代 row 数组，第一列替代 column 数组，可以将算法的空间复杂度降为O(1)，其具体步骤如下。

• (1) 检查第一行和第一列是否存在 0 元素，并根据结果设置 rowHasZero 和 columnHasZero

  的值（如果需要的话，稍后会将第一行和第一列清零）。

• (2) 遍历矩阵中的其余元素，如果 matrix[i][j]为 0，则将 matrix[i][0]和 matrix[0][j]置为 0。
• (3) 遍历矩阵中的其余元素，如果 matrix[i][0]为 0，则将第 i 行清零。

• (4) 遍历矩阵中的其余元素，如果 matrix[0][j]为 0，则将第 j 行清零。

  -(5) 根据第(1)步的结果，如果需要则将第一行和第一列清零。

void newSetZeros(int[][] matrix) {
boolean rowHasZero = false;
boolean columnHasZero = false;

// 检测第一行是否有0
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
rowHasZero = true;
break;
            }
        }
//检测第一列是否有0
for (int i = 0; i < matrix.length; i++){
if (matrix[i][0] == 0) {
columnHasZero = true;
break;
            }
        }

// 检测数组其余元素是否有0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
                }
            }
        }
// 根据第一列的值置空行
for (int i = 1; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
nullifyRow(matrix, i);
            }
        }
// 根据第一行的值置空列
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[0][j]== 0) {
nullifyColumn(matrix, j);
            }
        }

// 置空第一行
if (rowHasZero) {
nullifyRow(matrix, 0);
        }
// 指控第一列
if (columnHasZero) {
nullifyColumn(matrix, 0);
        }
    }

private void nullifyColumn(int[][] matrix, int column) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][column] = 0;
        }
    }

private void nullifyRow(int[][] matrix, int row) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[row][j] = 0;
        }
    }
}