[LeetCode]--73. Set Matrix Zeroes

简介: Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.click to show follow up.Follow up: Did you use extra space? A straight forward solution us

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

click to show follow up.

Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

这道题的要求是在m*n的矩阵中,如果某一元素是0,则将该行该列均置为0(原地处理哦)。

直接的方式,可以再开一个m*n的数组,用以标记0的位置,这样空间复杂度是O(mn)。当然也可以用长度为m和n的数组,分别标记行和列中出现0的位置,这样空间复杂度是O(m+n)。

进一步,可以把0出行的位置标记在第一行和第一列上,这样空间复杂度降低为O(1)了。

时间复杂度:O(mn)

空间复杂度:O(1)

public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        int first = 1;

        for (int i = 0; i < m; i++) {

            if (matrix[i][0] == 0) {
                first = 0;
            }

            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        // i需要从后往前,否则matrix[0][j]的值可能被改变
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++)
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            if (first == 0) {
                matrix[i][0] = 0;
            }
        }
    }
目录
相关文章
Leetcode 74. Search a 2D Matrix
这道题很简单,为此专门写篇博客其实算博客凑数了。给你一个每一行每一列都是增序,且每一行第一个数都大于上一行末尾数的矩阵,让你判断某个数在这个矩阵中是否存在。 假设矩阵是m*n,扫一遍的时间复杂度就是O(m*n),题目中给出的这么特殊的矩阵,时间复杂度可以降到O(m+n),具体代码如下,写的比较挫。
86 1
Leetcode 240. Search a 2D Matrix II
具体思路就是每一行倒着扫,扫到第一个比target小的数就跳到下行,如果等于当然是直接返回true了,如果下一行还比target小就继续跳下一行,直到最后一行。 为啥这么做是可行的? 可能我比较笨,想了半天才想到。 因为每一列都是增序的,举个例子,假设matrix[0][5] > target,那么[0][5]位置右下(包含右和下)所有元素不可能比target小。
48 0
|
Python
LeetCode 378. Kth S Element in a Sorted Matrix
给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第k小元素,而不是第k个元素。
108 0
LeetCode 378. Kth S Element in a Sorted Matrix
|
存储
LeetCode 329. Longest Increasing Path in a Matrix
给定一个整数矩阵,找出最长递增路径的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。
75 0
LeetCode 329. Longest Increasing Path in a Matrix
LeetCode 283. Move Zeroes
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
110 0
LeetCode 283. Move Zeroes
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
LeetCode 1380. 矩阵中的幸运数 Lucky Numbers in a Matrix
|
算法 Python
LeetCode 283. 移动零 Move Zeroes
LeetCode 283. 移动零 Move Zeroes
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
LeetCode 5340. 统计有序矩阵中的负数 Count Negative Numbers in a Sorted Matrix
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
121 2