leetcode73-矩阵置零

原题

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

示例 1:

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

进阶:

  • 一个直接的解决方案是使用  O(mn) 的额外空间,但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。
  • 你能想出一个常数空间的解决方案吗?

解法

思想

要使用原地算法,需要考虑如何记录下哪一行那一列需要变为0。

当我们在遍历矩阵的时候,如果扫描到一个0,那么这一行和这一列都应变为0,但是由于还有未扫描到的元素,所以不能贸然改变后面的元素,但可以改变左边和上面的元素,因为它们都已经扫描过了

于是可以这样:使用第一行和第一列的元素来标识是否有需要变为0的行和列,如果是,就将该元素设为0。但需要先扫描一遍第一行和第一列是否原先就有0,使用两个布尔值记录。

代码

class Solution {
    public void setZeroes(int[][] matrix) {
        if(matrix.length == 0) return;
        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRow = false;
        boolean firstCol = false;

        for(int i = 0;i < m;i++){
            for(int j = 0;j<n;j++){
                int item = matrix[i][j];
                if (item == 0) {
                    if (i == 0) firstRow = true;
                    if (j == 0) firstCol = true;
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int item = matrix[i][j];
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        // 修改第一行和第一列
        if (firstRow) {
            for (int i = 0; i < n; i++) 
                matrix[0][i] = 0;
        }

        if (firstCol) {
            for (int i = 0; i < m; i++)
                matrix[i][0] = 0;
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode73-%e7%9f%a9%e9%98%b5%e7%bd%ae%e9%9b%b6/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月13日 18:44
下一篇 2020年5月14日 22:40

相关推荐

  • leetcode836-矩形重叠

    原题 矩形以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。 如果相交的面积为正,则称两矩形重叠。需要…

    算法 2020年3月18日
    0440
  • leetcode652-寻找重复的子树

    原题 给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例1: 1 / \ 2…

    算法 2019年12月26日
    0310
  • leetcode4-寻找两个有序数组的中位数

    这道题我没想出符合条件的思路 原题 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m…

    算法 2020年1月9日
    0620
  • leetcode561-数组拆分I

    原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, b…

    算法 2019年11月18日
    080
  • 蓝桥杯试题-小数第n位

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述   我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。  如果我们把有限小数的末尾加上无限多个…

    算法 2020年2月29日
    080
  • leetcode841-钥匙和房间

    原题 有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,...,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。 在形式上,对于每个房间 i 都有一…

    2019年12月13日
    0110
  • leetcode622-设计循环队列

    设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是…

    算法 2019年11月24日
    0130
  • leetcode128-最长连续序列

    原题 给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长…

    算法 2020年6月6日
    080
  • leetcode2-两数相加

    原题 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回…

    算法 2019年12月17日
    070
  • leetcode8-字符串转换整数 (atoi)

    原题 请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下: 如果第一个…

    算法 2020年4月3日
    0270

发表回复

登录后才能评论