73. 矩阵置零(Set Matrix Zeroes) - 《leetcode》

来源
描述
题解

来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/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) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

题解

额外存储空间法

class Solution {
    public void setZeroes(int[][] matrix) {
        int R = matrix.length;
        int C = matrix[0].length;
        Set<Integer> rowSets = new HashSet<>();
        Set<Integer> columnSets = new HashSet<>();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (matrix[i][j] == 0) {
                    rowSets.add(i);
                    columnSets.add(j);
                }
            }
        }
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (rowSets.contains(i) || columnSets.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

复杂度分析

时间复杂度：，其中和分别对应行数和列数

空间复杂度： 73. 矩阵置零(Set Matrix Zeroes) - 图4

暴力法

上述方法使用额外空间去记录需要置零的行号和列号，但其实可以通过修改原始矩阵避免额外空间的消耗。
循环两遍，第一遍将符合条件的非零元素置为虚拟值(虚拟值的取值依赖于问题约束)；第二遍将虚拟值置为零

class Solution {
  public void setZeroes(int[][] matrix) {
      int MODIFIED = -1000000;
      int R = matrix.length;
      int C = matrix[0].length;
      for (int r = 0; r < R; r++) {
          for (int c = 0; c < C; c++) {
              if (matrix[r][c] == 0) {
                  for (int k = 0; k < C; k++) {
                      if (matrix[r][k] != 0) {
                          matrix[r][k] = MODIFIED;
                      }
                  }
                  for (int k = 0; k < R; k++) {
                      if (matrix[k][c] != 0) {
                          matrix[k][c] = MODIFIED;
                      }
                  }
              }
          }
      }
      for (int r = 0; r < R; r++) {
          for (int c = 0; c < C; c++) {
              if (matrix[r][c] == MODIFIED) {
                  matrix[r][c] = 0;
              }
          }
      }
  }
}

复杂度分析

时间复杂度：，其中和分别对应行数和列数。尽管这个方法避免了使用额外空间，但是效率很低：当每个元素都为零时，我们需要访问所有的行和列。

空间复杂度： 73. 矩阵置零(Set Matrix Zeroes) - 图8

优化法

上述暴力法的缺点是存在大量冗余赋值。我们可以用每行和每列的第一个元素作为标记，表示这一行或者这一列是否需要赋零。
注意点：第一行和第一列的标记位由于会重复，故第一列的标记位使用单独的变量，第一行的标记位使用 73. 矩阵置零(Set Matrix Zeroes) - 图9

class Solution {
  public void setZeroes(int[][] matrix) {
      int R = matrix.length;
      int C = matrix[0].length;
      boolean isColumn = false;
      for (int i = 0; i < R; i++) {
          if (matrix[i][0] == 0) isColumn = true;
          for (int j = 1; j < C; j++) {
              if (matrix[i][j] == 0) {
                  matrix[i][0] = 0;
                  matrix[0][j] = 0;
              }
          }
      }
      for (int i = 1; i < R; i++) {
          for (int j = 1; j < C; j++) {
              if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                  matrix[i][j] = 0;
              }
          }
      }
      // 第一行
      if (matrix[0][0] == 0) {
          for (int j = 0; j < C; j++) {
              matrix[0][j] = 0;
          }
      }
      // 第一列
      if (isColumn) {
          for (int i = 0; i < R; i++) {
              matrix[i][0] = 0;
          }
      }
  }
}

复杂度分析

时间复杂度：
空间复杂度：