题目描述

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

样例

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

输入: 
[
  [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) 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个常数空间的解决方案吗？

算法分析

模拟

• 1、遍历整个矩阵，如果当前位置matrix[i,j] == 0，则在第i行的第一个元素，和第j列的第一个元素进行标记（绿色区域），表示第i行和第j列的所有元素都需要置换成0
• 2、为了避免二次置换，进行下面两个操作 -------- 将黄色区域进行置换
  • 需要行i从1枚举到n - 1，如果第i行的第一个元素被标记过，则将整行赋值为0
  • 需要行j从1枚举到m - 1，如果第j列的第一个元素被标记过，则将整列赋值为0
• 3、用r标记第0行是否存在0的元素，用c标记第0列是否存在0的元素，1表示不存在，0表示存在，最后若r == 0，把第0行全部置换成0，c == 0，把第0列全部置换成0

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        int r = 1,c = 1;
        for(int i = 0;i < n;i ++)
            for(int j = 0;j < m;j ++)
                if(matrix[i][j] == 0)
                {
                    if(i == 0) r = 0;//表示第0行存在0
                    if(j == 0) c = 0;//表示第0列存在0 
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }

        for(int i = 1;i < n;i ++)
        {
            if(matrix[i][0] == 0)
                for(int j = 1;j < m;j ++)
                    matrix[i][j] = 0;
        }
        for(int j = 1;j < m;j ++)
        {
            if(matrix[0][j] == 0)
                for(int i = 1;i < n;i ++)
                    matrix[i][j] = 0;
        }

        if(r == 0) for(int j = 0;j < m;j ++) matrix[0][j] = 0;
        if(c == 0) for(int i = 0;i < n;i ++) matrix[i][0] = 0;

    }
}