LeetCode 73. 矩阵置零 (标记数组)

阳光穿透心脏的1/2处 2024-05-08 06:18 51阅读 0赞

##### 题目 #####

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

**进阶：**

*  一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
 *  一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
 *  你能想出一个仅使用常量空间的解决方案吗？

**示例 1：**

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

**示例 2：**

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
    输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

**提示：**

m == matrix.length
    n == matrix[0].length
    1 <= m, n <= 200
    -231 <= matrix[i][j] <= 231 - 1

##### 思路 #####

需要遍历两趟原数组，第一次遍历时找到零元素所在行和所在列，并记录下来；  
第二趟遍历时，查看当前元素所在行和所在列是否被标记过，若被标记过，则需要改为零；

##### 代码 #####

class Solution {
        
        public void setZeroes(int[][] matrix) {
        
            int m = matrix.length, n = matrix[0].length;
            boolean[] row = new boolean[m];
            boolean[] col = new boolean[n];
            for(int i = 0; i < m; i ++) {
        
                for(int j = 0; j < n; j ++) {
        
                    if(matrix[i][j] == 0) {
        
                        row[i] = col[j] = true;
                    }
                }
            }
            //更新原矩阵
            for(int i = 0; i < m; i ++) {
        
                for(int j = 0; j < n; j ++) {
        
                    if(row[i] || col[j]) matrix[i][j] = 0;
                }
            }
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，51人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode 73. 矩阵置零 (标记数组)

题目给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。进阶：一个直观的解决方案是使用 O(mn) 的额外空...

阳光穿透心脏的1/2处/ 2024年05月08日 06:18/ 0 赞/ 52 阅读

相关 73. 矩阵置零

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

悠悠/ 2023年10月04日 08:22/ 0 赞/ 24 阅读

相关【LeetCode 73】矩阵置零

题目描述给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。示例 1: 输入: [

淡淡的烟草味﹌/ 2022年11月27日 15:38/ 0 赞/ 124 阅读

相关 LeetCode73. 矩阵置零

难度：`中等` 题目描述： > 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。进阶： > 一个直观

你的名字/ 2022年11月12日 01:45/ 0 赞/ 154 阅读

相关 LeetCode 73. 矩阵置零——每日一题

上一篇博客：[堆优化版Dijkstra算法][Dijkstra] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个

Love The Way You Lie/ 2022年11月12日 01:38/ 0 赞/ 119 阅读

相关 LeetCode73. 矩阵置零

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

电玩女神/ 2022年05月12日 01:22/ 0 赞/ 152 阅读

相关 LeetCode 73.Set Matrix Zeroes (矩阵置零)

题目描述：给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用[原地][Link 1]算法。示例 1: 输入:

青旅半醒/ 2022年05月10日 08:38/ 0 赞/ 172 阅读

相关 Leetcode算法Java全解答--73. 矩阵置零

Leetcode算法Java全解答–73. 矩阵置零文章目录 Leetcode算法Java全解答--73. 矩阵置零题目想法

落日映苍穹つ/ 2022年04月04日 07:28/ 0 赞/ 171 阅读

相关 leetcode:73. 矩阵置零

题目: 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。示例 1: 输入: \[ \[1,1,1\]

╰半橙微兮°/ 2022年03月20日 07:12/ 0 赞/ 204 阅读

相关【LeetCode】 73. 矩阵置零空间O(1)

<table> <tbody> <tr> <td><font>题目</font></td> </tr> </tbody> </table>

古城微笑少年丶/ 2021年06月10日 20:38/ 0 赞/ 338 阅读