LeetCode第73题矩阵置零

简介: 文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。

继续打卡算法题,今天学习的是LeetCode第73题矩阵置零,这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些提升。

image.png

分析一波题目

这个题目最直观的做法是使用一个二维数组,将每行/每列是否有0记录下来。然后再遍历一次矩阵进行置0操作。 这样空间复杂度是O(mn).

有没有其他更优的方法呢?

我们可以使用矩阵数组的第一行,第一列来存储某行某列是否有0标记,然后使用两个遍历来存储第一行,第一列的是否有0标记。

image.png

这样空间复杂度变成了O(1)。

本题解题技巧

1、使用原矩阵第一行,第一列记录某行,某列是否存在0的标记,减少了额外空间存储

编码解决

class Solution {
   
   
    public void setZeroes(int[][] matrix) {
   
   
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false, flagRow0 = false;
        for (int i = 0; i < m; i++) {
   
   
            if (matrix[i][0] == 0) {
   
   
                flagCol0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
   
   
            if (matrix[0][j] == 0) {
   
   
                flagRow0 = true;
            }
        }
        for (int i = 1; i < m; i++) {
   
   
            for (int j = 1; j < n; j++) {
   
   
                if (matrix[i][j] == 0) {
   
   
                    matrix[i][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 (flagCol0) {
   
   
            for (int i = 0; i < m; i++) {
   
   
                matrix[i][0] = 0;
            }
        }
        if (flagRow0) {
   
   
            for (int j = 0; j < n; j++) {
   
   
                matrix[0][j] = 0;
            }
        }
    }
}

总结

1、二维数组遍历的题目,今天又学到了一个技巧,第一行第一列存储标记在本题应用上是非常巧妙的。

相关文章
|
7月前
|
算法
力扣240 搜索二维矩阵II
力扣240 搜索二维矩阵II
|
7月前
|
算法 测试技术 C#
【二分查找】LeetCode1970:你能穿过矩阵的最后一天
【二分查找】LeetCode1970:你能穿过矩阵的最后一天
|
7月前
leetcode-329:矩阵中的最长递增路径
leetcode-329:矩阵中的最长递增路径
53 0
|
2月前
|
算法 C++
Leetcode第59题(螺旋矩阵2)
这篇文章介绍了解决LeetCode第59题“螺旋矩阵II”的算法,通过C++编程实现按顺时针顺序填充一个n x n的正方形矩阵。
18 0
|
4月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
52 6
|
4月前
|
算法 JavaScript Python
【Leetcode刷题Python】79. 单词搜索和剑指 Offer 12. 矩阵中的路径
Leetcode第79题"单词搜索"的Python解决方案,使用回溯算法在给定的二维字符网格中搜索单词,判断单词是否存在于网格中。
46 4
|
4月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
34 0
【Leetcode刷题Python】73. 矩阵置零
|
6月前
|
算法
力扣经典150题第三十七题:矩阵置零
力扣经典150题第三十七题:矩阵置零
33 2
|
6月前
|
存储 数据采集 算法
LeetCode题目73:矩阵置零
LeetCode题目73:矩阵置零
|
6月前
力扣随机一题 6/28 数组/矩阵
力扣随机一题 6/28 数组/矩阵
46 0