力扣第73题-矩阵置零

题目
题目链接

题解

class Solution {
    public void setZeroes(int[][] matrix) {
         constSpace(matrix);
         //useHashTable(matrix);
    }

    // 使用常规哈希表解法
    private void useHashTable(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return;
        }
        boolean[] row = new boolean[matrix.length], col = new boolean[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    // 使用常量空间
    private void constSpace(int[][] matrix) {
        // 标记第一行和第一列是否有0
        boolean srz = false, scz = false;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                scz = true;
                break;
            }
        }
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[0][j] == 0) {
                srz = true;
                break;
            }
        }
        // 遍历全数组，将0记录到第一行和第一列
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        // 再次遍历数组，通过第一行第一列的记录将对应的行和列置为0
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 通过标记将第一行或者第一列整行整列置为0
        if (srz) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[0][j] = 0;
            }
        }
        if (scz) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}