描述

Given a m × n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up: Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

分析

O(mn)空间复杂度

这种方法最简单粗暴,直接克隆一个和matrix等大的二维数组,然后先逐行后逐列扫描,当遇到0设置新matrix的行或者列为0,最后将克隆matrix复制给原matrix即可

O(m+n)空间复杂度

创建长度为m的一维数组缓存matrix各行中是否有0,创建长度为n的一维数组缓存matrix各列中是否由0,最后更新matrix。ps:根据数组缓存各行各列是否存在0很容易由O(m+n)的空间复杂度联想到,但缓存的方式也不一定要使用数组,如(i, j)这样的数值对也很容易联想到Map,以行为key,列为value,但是注意value值覆盖问题(2行1列和2行3列会相互覆盖,需要使用一个LinkedList作为value解决覆盖)

常量空间复杂度

常量空间的方式只是将缓存的信息放在了原matrix中,巧妙利用matrix第一行第一列来缓存matrix各行各列是否有0。

  1. 先扫描第一行第一列,如果有0,则将各自的flag设置为true
  2. 然后扫描除去第一行第一列的整个数组,如果有0,则将对应的第一行和第一列的数字赋0
  3. 再次遍历除去第一行第一列的整个数组,如果对应的第一行和第一列的数字有一个为0,则将当前值赋0
  4. 然后根据第一行第一列的flag来更新第一行第一列

代码

常量空间算法

public void setMatrixZeroes(int[][] nums){
    boolean rowFlag = false;
    boolean colFlag = false;
    
    //1.遍历第一行第一列查看是否有0存在
    for(int i = 0; i < nums[0].length; i++){
        if(nums[0][i] == 0){
            //第一行有0存在
            rowFlag = true;
        }
    }
    for(int i = 0; i < nums.length; i++){
        if(nums[i][0] == 0){
            //第一列有0存在
            colFlag = true;
        }
    }
        
    //2.遍历第一行第一列之外的数组查看是否有0存在
    for(int i = 1; i < nums.length; i++){
        for(int j = 1; j < nums[i].length; j++){
            if(nums[i][j] == 0){
                //对应的第一行和第一列的数字赋0
                nums[0][j] = 0;
                nums[i][0] = 0;
            }
        }
    }
        
    //3.遍历第一行第一列之外的数组,如果相应的第一行第一列有0存在,则设置为0
    for(int i = 1; i < nums.length; i++){
        for(int j = 1; j < nums[i].length; j++){
            if(nums[0][j] == 0 || nums[i][0] == 0){
                nums[i][j] = 0;
            }
        }
    }
        
    //4.根据第一行第一列的flag来更新第一行第一列
    if(rowFlag){
        for(int i = 0; i < nums[0].length; i++){
            nums[0][i] = 0;
        }
    }
    if(colFlag){
        for(int i = 0; i < nums.length; i++){
            nums[i][0] = 0;
        }
    }
}
版权声明:本文为wxiaoqi原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://www.cnblogs.com/wxiaoqi/p/9536445.html