X

LEETCODE 73. Set Matrix Zeroes 解题思路分析

题目大意:

矩阵置零

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=73

解题思路分析:

题目在进阶中给出了三种解决方案,我们一一来分析一下。

解法一,使用 O(mn) 的额外空间,这种做法比较直接并简单,我们利用原数组copy出一个新数组,遍历新数组中每一个元素,如果是0,则在原数组将该位置对应的行和列都置换为0即可。代码简单,时间复杂度为m*n,空间复杂度也是m*n。

解法二,使用 O(m + n) 的额外空间,我们建立2个boolean型数组,一个代表行,一个代表列。遍历数组中每一个元素,如果是0,表示当前行上存在0,并且当前列上存在0,更新两个boolean数组相对应的行和列,将值更新为true。最后再分别循环一遍2个boolean数组,查看哪些行和列上存在0,就将这些行和列都置换为0。本解法时间复杂度是 m*n,空间复杂度是m+n。

解法三,使用常数级别空间。所谓常数空间就是不能定义数组,只能定义一些基本类型的变量。解题思路其实与解法二类似,只不过我们不需要定义2个boolean型数组。实现上依旧先循环一遍数组中每个元素,如果当前元素是0,那么我们将该元素所在行和列的首元素更改为0,代表改行和列上存在数字0。然后我们再遍历一遍数组,如果该行或者列上的首元素是0,那么我们就将当前元素置换为0。这里需要注意一点,本次循环我们要从行和列下标为1的位置开始循环,如果从0开始循环,可能会将首行或者首列都置换成0,这样会影响接下来的判断。因此本次循环完之后,我们还需要再分别判断一下原数组首行和首列是否包含0,再决定是否将首行和首列都置换为0。本解法时间复杂度是 m*n,空间复杂度是1。

实现代码:

public void setZeroes(int[][] matrix) {
    // 首行是否包含0
    boolean firstRowHasZero = false;
    // 首列是否包含0
    boolean firstColHasZero = false;
    // 遍历每一个元素
    for(int r=0;r<matrix.length;r++){
        for(int c=0;c<matrix[0].length;c++){
            // 如果当前元素为0
            if(matrix[r][c]==0){
                // 如果当前是首行,则首行包含0
                if(r==0) firstRowHasZero=true;
                // 如果当前是首列,首列包含0
                if(c==0) firstColHasZero=true;
                // 将当前元素所在列的首元素置换为0
                matrix[r][0]=0;
                // 将当前元素所在行的首元素置换为0
                matrix[0][c]=0;
            }
        }
    }
    // 循环除去首行和首列的每一个元素
    for(int r=1;r<matrix.length;r++){
        for(int c=1;c<matrix[0].length;c++){
            // 如果当前元素所在行或者所在列包含0,当前元素置换为0
            if(matrix[r][0]==0||matrix[0][c]==0){
                matrix[r][c]=0;
            }
        }
    }
    // 如果首列包含0,将首列置换为0
    if(firstColHasZero){
        for(int r=0;r<matrix.length;r++){
            matrix[r][0]=0;
        }
    }
    // 如果首行包含0,将首行置换为0
    if(firstRowHasZero){
        for(int c=0;c<matrix[0].length;c++){
            matrix[0][c]=0;
        }
    }
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 40.19% of Java online submissions for Set Matrix Zeroes.

Memory Usage: 68.5 MB, less than 5.71% of Java online submissions for Set Matrix Zeroes.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-73-set-matrix-zeroes-解题思路分析/
Categories: leetcode
kwantong: