矩阵置零

题面

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

示例 1：

输入： matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入： matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

进阶：

• 一个直观的解决方案是使用 O(m n) 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个仅使用常量空间的解决方案吗？

分析

• 最直观的方法是创建一个新的数组，初始化为 -1，当遇到非零数字时，填入新数组，当遇到 0 时，就将新数组的对应列和行置为 0，其空间复杂度为 $O(mn)$

• 这个空间复杂度可以继续进行优化吗？可以只存储某一行和某一列是否被置为 0，遍历完所有元素后，即可重新遍历，进行置零操作，其空间复杂度为 $O(m+n)$

• 那么可以继续优化，只使用常量空间吗？也即能够进行原地操作吗？

• 原地操作的一个问题是，当遇到 0 时，如果直接更新数组，之和还会再碰到 0，这样就会导致错误的更新为 0；同时也会覆盖原先可能存在的 0

• 可以在需要被置换为 0 的行和列的开头设置标记，来表示对应行和列要被置换为 0；这样，即使对于原本是 0 的位置，也不会造成影响

• 注意边界情况是 matrix[0][0]，要记录其等于 0 是由于谁导致的，即是否将第一行/第一列置为 0

• 代码实现

  class Solution {
  public:
      void setZeroes(vector<vector<int>>& matrix) {
          bool firstColumn = false;
          bool firstRow = false;
          for (int i = 0; i < matrix.size(); i++) {
              for (int j = 0; j < matrix[i].size(); j++) {
                  if (matrix[i][j] == 0 && (i != 0 && j != 0)) {
                      matrix[i][0] = matrix[0][j] = 0;
                  }
                  firstColumn = firstColumn || (matrix[i][j] == 0 && j == 0);
                  firstRow = firstRow || (matrix[i][j] == 0 && i == 0);
              }
          }
          for (int i = 1; i < matrix.size(); i++) {
              if (matrix[i][0] == 0) {
                  for (int j = 0; j < matrix[i].size(); j++) {
                      matrix[i][j] = 0;
                  }
              }
          }
          for (int j = 1; j < matrix[0].size(); j++) {
              if (matrix[0][j] == 0) {
                  for (int i = 0; i < matrix.size(); i++) {
                      matrix[i][j] = 0;
                  }
              }
          }
          if (firstColumn) {
              for (int i = 0; i < matrix.size(); i++) {
                  matrix[i][0] = 0;
              }
          }
          if (firstRow) {
              for (int j = 0; j < matrix[0].size(); j++) {
                  matrix[0][j] = 0;
              }
          }
      }
  };

• 可以对以上方法进一步优化，只使用一个标记遍历记录第一列是否原本存在 0，这样第一列的第一个元素即可以标记第一行是否出现 0

• 但为了防止每一列的第一个元素被提前更新，需要从最后一行开始，倒序地处理矩阵元素

• 代码实现

  class Solution {
  public:
      void setZeroes(vector<vector<int>>& matrix) {
          int m = matrix.size();
          int n = matrix[0].size();
          int flag_col0 = false;
          for (int i = 0; i < m; i++) {
              if (!matrix[i][0]) {
                  flag_col0 = true;
              }
              for (int j = 1; j < n; j++) {
                  if (!matrix[i][j]) {
                      matrix[i][0] = matrix[0][j] = 0;
                  }
              }
          }
          for (int i = m - 1; i >= 0; i--) {
              for (int j = 1; j < n; j++) {
                  if (!matrix[i][0] || !matrix[0][j]) {
                      matrix[i][j] = 0;
                  }
              }
              if (flag_col0) {
                  matrix[i][0] = 0;
              }
          }
      }
  };