矩阵

矩阵置零

中等#73Java时间 O(m n)空间 O(1)

题目要做什么

矩阵中原本为 0 的元素,其所在整行和整列都要变为 0。原地修改,使用常数额外空间。

题目示例输入matrix = [[1,1,1],[1,0,1],[1,1,1]]
题目示例输出[[1,0,1],[0,0,0],[1,0,1]]

01 为什么这样做

用第一行和第一列保存清零标记。因为标记会占用它们,需要另外记录第一行、第一列原本是否含零。先打标记,再处理内部,最后处理标记所在边界。

始终成立的条件

内部扫描阶段只修改第一行和第一列,不修改尚未扫描的内部值,防止新零引发错误传播。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public void setZeroes(int[][] matrix) {3        int rows = matrix.length, columns = matrix[0].length;4        boolean firstRow = false, firstCol = false;5        for (int c = 0; c < columns; c++) if (matrix[0][c] == 0) firstRow = true;6        for (int r = 0; r < rows; r++) if (matrix[r][0] == 0) firstCol = true;7        for (int r = 1; r < rows; r++) {8            for (int c = 1; c < columns; c++) {9                if (matrix[r][c] == 0) {10                    matrix[r][0] = 0; matrix[0][c] = 0;11                }12            }13        }14        for (int r = 1; r < rows; r++) {15            for (int c = 1; c < columns; c++) {16                if (matrix[r][0] == 0 || matrix[0][c] == 0) matrix[r][c] = 0;17            }18        }19        if (firstRow) Arrays.fill(matrix[0], 0);20        if (firstCol) for (int r = 0; r < rows; r++) matrix[r][0] = 0;21    }22}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索