18.矩阵置零

raylan.chen大约 2 分钟

class Solution {
    public void setZeroes(int[][] matrix) {
        // 1、先遍历一遍矩阵，存储「0 索引」
        // 2、再根据存储的索引，将其所在行和列置0
        // 时间：O(mn + max(m, n)), 空间：O(mn)

        // 改进：记录需要置0的行和列
        // 时间：O(4mn)，空间：O(m + n)
        
        int m = matrix.length;
        int n = matrix[0].length;
        // 存储「0 索引」
        boolean[] tmpArr = new boolean[m + n];
        Arrays.fill(tmpArr, false);
        // 1️⃣
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    tmpArr[i] = true;
                    tmpArr[m + j] = true;
                }
            }
        }
        // 2️⃣
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (tmpArr[i] || tmpArr[m + j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

优秀题解

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row = len(matrix)
        col = len(matrix[0])
        row0_flag = False
        col0_flag = False
        # 找第一行是否有0
        for j in range(col):
            if matrix[0][j] == 0:
                row0_flag = True
                break
        # 第一列是否有0
        for i in range(row):
            if matrix[i][0] == 0:
                col0_flag = True
                break

        # 把第一行或者第一列作为 标志位
        for i in range(1, row):
            for j in range(1, col):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0
        #print(matrix)
        # 置0
        for i in range(1, row):
            for j in range(1, col):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0

        if row0_flag:
            for j in range(col):
                matrix[0][j] = 0
        if col0_flag:
            for i in range(row):
                matrix[i][0] = 0

作者：powcai
链接：https://leetcode.cn/problems/set-matrix-zeroes/solutions/6594/o1kong-jian-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

模范 Python 编写 Java 版本：

class Solution {
    public void setZeroes(int[][] matrix) {
        // 把第一行和第一列作为标志位
        // 1、检查第一行和第一列是否有零值
        boolean row = false;
        boolean col = false;
        int m = matrix.length;
        int n = matrix[0].length;
        // 第一行
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                row = true;
                break;
            }
        }
        // 第一列
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                col = true;
                break;
            }
        }
        // 检查 1~m-1 行 以及 1~n-1 列是否有零值，并且将第一行和第一列当作标志位
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][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;
                }
            }
        }
        // 第一行和第一列是否需要置零检查
        if (row) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

18.矩阵置零

18.矩阵置零

参考链接

个人尝试

优秀题解