程式員面試金典-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;
        }
    }
}