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;
                }
            }
        }
    }
    

    相关文章

      网友评论

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

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