leetcode 73. 矩阵置零

作者: topshi | 来源:发表于2019-04-22 14:24 被阅读13次

题目描述

给定一个 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) 的额外空间,但这仍然不是最好的解决方案。
  • 你能想出一个常数空间的解决方案吗?

思路:

  • 一种直接的解决方案是另开一个同样大小的矩阵,通过扫描原矩阵在新矩阵做赋值。
  • 一个简单的改进方案使用O(m + n),可以定义两个数组一个长度为m,一个长度为n标记需要置零的行和列。
  • 常量级空间的方案是基于第二个方法的改进,我们将矩阵的第一列看成长度为m-1的数组,第一行看成长度为n-1的数组,用它们来标记它们右下角大小为(m - 1) * (n - 1)的数组需要置零的行和列,这就变成了第二个方法的解法,只需要另外定义两个变量rowFlagcolFlag标记第一行和第一列本来有没有含有0

匈牙利著名数学家罗莎·彼得在他的名著《无穷的玩艺》中,通过一个十分生动而有趣的笑话,来说明数学家是如何用化归的思想方法来解题的。有人提出了这样一个问题:“假设在你面前有煤气灶,水龙头、水壶和火柴,你想烧开水,应当怎样去做?”对此,某人回答说:“在壶中灌上水,点燃煤气,再把壶放在煤气灶上。”提问者肯定了这一回答,但是,他又追问道:“如果其他的条件都没有变化,只是水壶中已经有了足够的水,那么你又应该怎样去做?”这时被提问者一定会大声而有把握地回答说:“点燃煤气,再把水壶放上去。”但是更完善的回答应该是这样的:“只有物理学家才会按照刚才所说的办法去做,而数学家却会回答:‘只须把水壶中的水倒掉,问题就化归为前面所说的问题了’”。我们将原矩阵切两刀把右下角大小为(m-1)*(n-1)的矩阵和第一行、第一列切出来,就可以使用常量空间而变成了第二种方法的解法,最后对第一行和第一列做下置零处理即可。

class Solution {
    //用矩阵的第一行保存需要置零的列,第一列保存需要置零的行
    //rowFlag,colFlag分别标记第一行和第一列本来有没有0
    public void setZeroes(int[][] matrix) {
        boolean rowFlag = false, colFlag = false;
        //第一列是否含有0
        for(int row = 0; row < matrix.length;row++){
            if(matrix[row][0] == 0){
                colFlag = true;
                break;
            }   
        }
        //第一行是否含有0
        for(int col = 0; col < matrix[0].length;col++){
            if(matrix[0][col] == 0){
                rowFlag = true;
                break;
            }   
        }
        
        for(int row = 1;row < matrix.length;row++){
            for(int col = 1;col < matrix[0].length;col++){
                if(matrix[row][col] == 0){
                    matrix[row][0] = 0;
                    matrix[0][col] = 0;
                }
            }
        }
        //将行置零
        for(int row = 1;row < matrix.length;row++){
            if(matrix[row][0] == 0){
                for(int col = 1;col < matrix[0].length;col++){
                    matrix[row][col] = 0;
                }
            }
        }
        //将列置零
        for(int col = 1;col < matrix[0].length;col++){
            if(matrix[0][col] == 0){
                for(int row = 1;row < matrix.length;row++){
                    matrix[row][col] = 0;
                }
            }
        }
        //第一行置零
        if(rowFlag == true){
            for(int col = 0;col < matrix[0].length;col++){
                matrix[0][col] = 0;
            }
        }
        //第一列置零
        if(colFlag == true){
            for(int row = 0;row < matrix.length;row++){
                matrix[row][0] = 0;
            }
        }
    }
}

相关文章

  • 73 矩阵清零

    73. 矩阵置零[https://leetcode-cn.com/problems/set-matrix-zero...

  • leetcode 73. 矩阵置零

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

  • LeetCode题解 - 73. 矩阵置零

  • LeetCode-python 73.矩阵置零

    题目链接难度:中等 类型: 数组 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在...

  • LeetCode 力扣 73. 矩阵置零

    题目描述(中等难度) 给定一个矩阵,然后找到所有含有 0 的地方,把该位置所在行所在列的元素全部变成 0。 解法一...

  • 73.矩阵置零

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

  • 73. 矩阵置零

    https://leetcode-cn.com/problems/set-matrix-zeroes/

  • 73.矩阵置零

    原题 https://leetcode-cn.com/problems/set-matrix-zeroes/ 解题...

  • 73. 矩阵置零

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

  • python实现leetcode之73. 矩阵置零

    解题思路 第一步,找出出现0的行列第二步,对出现0的行清0第三步,对出现0的列清0 73. 矩阵置零[https:...

网友评论

    本文标题:leetcode 73. 矩阵置零

    本文链接:https://www.haomeiwen.com/subject/sueygqtx.html