矩陣置零

LeetCode 73

https://leetcode-cn.com/problems/set-matrix-zeroes/

解題思路：

• 本題很容易想到空間復雜度為 O(mn)的解法，用一個boolean矩陣來標記每一個位置是否為空，最后再進行歸0操作，也算是暴力解決了。
• 下面提供一種狀態(tài)壓縮的方式，我們可以用原有的第0列和第0行來做標記，標記 row(1~row) col (1~col)這部分矩陣。至于原矩陣的第0行/列，可以用兩個變量來記錄是否要置0，在最開始進行判斷，然后第0行/列就用來記錄小矩陣，最后再處理第0行/列。

public class Solution {

    public void setZeroes(int[][] matrix) {
        int row = matrix.length, col = matrix[0].length;
        boolean isRow0 = false, isCol0 = false;
        // 判斷第0列是否存在 0，一旦存在則在后面會將這一列全部歸0
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                isCol0 = true;
                break;
            }
        }
        // 同上判斷第0行是否存在0
        for (int j = 0; j < col; j++) {
            if (matrix[0][j] == 0) {
                isRow0 = true;
                break;
            }
        }
        // 標記好后第0列/行后，將作為判斷內(nèi)部矩陣是否存在0的標志數(shù)組
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        // 根據(jù)第0列/行記錄的結果將對應行列進行歸0操作
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 最后將第0列和行判斷歸0
        if (isCol0) {
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
        if (isRow0) {
            for (int j = 0; j < col; j++) {
                matrix[0][j] = 0;
            }
        }
    }

}