题目描述

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

题目分析

开辟两个数组，用于记录哪一行有0，哪一列有0
再枚举每一个元素，检查它的行和列是否曾被记录有0，如果是，则把当前元素修改为0
时间复杂度 O(m * n)，空间复杂度 O(m + n)

空间上可以进一步优化，以每一行/列第一个元素来记录这行/列有没有0
但第一行和第一列的第一个元素是同一个，会产生冲突，所以第一行和第一列单独开个变量来记录是否有0
时间复杂度 O(m * n)，空间复杂度 O(1)

Java

public void setZeroes1(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    boolean[] zeroX = new boolean[m];
    boolean[] zeroY = new boolean[n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                zeroX[i] = true;
                zeroY[j] = true;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (zeroX[i] || zeroY[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

public void setZeroes2(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    boolean zeroX0 = false, zeroY0 = false;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 0) {
                if (i == 0) {
                    zeroX0 = true;
                }
                if (j == 0) {
                    zeroY0 = true;
                }
                if (i != 0 && j != 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
    }

    // 先处理后面的，防止第一行第一列被污染
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }
    // 处理第一列
    for (int i = 0; i < m; i++) {
        if (zeroY0) {
            matrix[i][0] = 0;
        }
    }
    // 处理第一行
    for (int j = 0; j < n; j++) {
        if (zeroX0) {
            matrix[0][j] = 0;
        }
    }
}

Kotlin

fun setZeroes1(matrix: Array<IntArray>): Unit {
    val m = matrix.size
    val n = matrix[0].size
    val zeroX = BooleanArray(m)
    val zeroY = BooleanArray(n)
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (matrix[i][j] == 0) {
                zeroX[i] = true
                zeroY[j] = true
            }
        }
    }
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (zeroX[i] || zeroY[j]) {
                matrix[i][j] = 0
            }
        }
    }
}

fun setZeroes2(matrix: Array<IntArray>): Unit {
    val m = matrix.size
    val n = matrix[0].size
    var zeroX0 = false
    var zeroY0 = false
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (matrix[i][j] == 0) {
                if (i == 0) {
                    zeroX0 = true
                }
                if (j == 0) {
                    zeroY0 = true
                }
                if (i > 0 && j > 0) {
                    matrix[i][0] = 0
                    matrix[0][j] = 0
                }
            }
        }
    }
    for (i in 1 until m) {
        for (j in 1 until n) {
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0
            }
        }
    }
    for (i in 0 until m) {
        if (zeroY0) {
            matrix[i][0] = 0
        }
    }
    for (j in 0 until n) {
        if (zeroX0) {
            matrix[0][j] = 0
        }
    }
}