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

相关推荐

  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器,使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数,或者是另一个列表。 示例1: 输入: [[1,1],2,[1,1]]…

    算法 2020年1月27日
    050
  • leetcode22-括号生成

    原题 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例: 输入:n = 3 输出:[ "((()))", "(()())", "…

    算法 2020年4月9日
    0130
  • leetcode295-数据流的中位数

    原题 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.…

    算法 2020年2月12日
    0130
  • leetcode701-二叉搜索树中的插入操作

    原题 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意,可能存在多种有效的插入方式,只…

    算法 2020年1月16日
    0110
  • leetcode119-杨辉三角II

    原题 给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。在杨辉三角中,每个数是它左上方和右上方的数的和。 示例: 输入: 3 输出: [1,3,3,1] 进阶: …

    2019年11月22日
    0280
  • leetcode349-两个数组的交集

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2] 示例2: 输入: nums1 = [4…

    算法 2019年12月14日
    090
  • leetcode1115-交替打印FooBar

    原题 我们提供一个类: class FooBar { public void foo() {     for (int i = 0; i < n; i++) {       …

    算法 2020年2月2日
    0180
  • leetcode95-不同的二叉搜索树II

    原题 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 示例: 输入: 3 输出: [   [1,null,3,2],  &n…

    算法 2020年1月22日
    0710
  • leetcode41-缺失的第一个正数

    原题 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3…

    算法 2020年5月11日
    0130
  • leetcode67-二进制求和

    原题 给定两个二进制字符串,返回他们的和(用二进制表示)。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = “11”, b = “1” 输出: “100” …

    算法 2019年11月15日
    0100

发表回复

登录后才能评论