Leetcode—矩阵置零

矩阵置零

给定一个 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]]

方法1

• 分析：根据题目所描述，我们可以先遍历数组找出所有0所在的位置，同时把这些位置对应标记在另一个数组temp中（即置这些位置上的值为1）；在遍历temp数组，找出置为1的位置，将对应matrix数组的行和列置为0即可。
• 方法1代码实现

  class Solution {
      public void setZeroes(int[][] matrix) {
          int rows = matrix.length;
          int cols = matrix[0].length;
          int[][] temp=new int[rows][cols];
          int flag=0;
          for(int i=0;i<rows;i++){
              for(int j=0;j<cols;j++){
                  if(matrix[i][j]==0){
                      temp[i][j]=1;
                  }
              }
          }
          for(int i=0;i<rows;i++){
              for(int j=0;j<cols;j++){
                  if(temp[i][j]==1){
                      for(int k=0;k<rows;k++){
                          matrix[k][j]=0;
                      }
                      for(int k=0;k<cols;k++){
                          matrix[i][k]=0;
                      }
                  }
              }
          }
      }
  }
  

• 优化：可以将temp改成两个数组，分别记录每一行和每一列是否有零出现，可以减少内存空间的占用，使空间复杂度变为O（m+n）

  class Solution {
      public void setZeroes(int[][] matrix) {
          int rows = matrix.length;
          int cols = matrix[0].length;
          boolean[] row = new boolean[rows];
          boolean[] col = new boolean[cols];
          for (int i = 0; i < rows; i++) {
              for (int j = 0; j < cols; j++) {
                  if (matrix[i][j] == 0) {
                      row[i] = col[j] = true;
                  }
              }
          }
          for (int i = 0; i < rows; i++) {
              for (int j = 0; j < cols; j++) {
                  if (row[i] || col[j]) {
                      matrix[i][j] = 0;
                  }
              }
          }
      }
  }
  

方法2

• 分析：用矩阵的第一行和第一列代替方法一中的两个标记数组。因为我们不确定第一行和第一列本身有没有0，所有要先判断它们有没有0（即标记两个标记变量为true）。接着，循环判断用其他行与列，来标记第一行与第一列。然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。

• 代码实现

  class Solution {
      public void setZeroes(int[][] matrix) {
          int rows = matrix.length;
          int cols = matrix[0].length;
          boolean flagCol0 = false, flagRow0 = false;
          for (int i = 0; i < rows; i++) {
              if (matrix[i][0] == 0) {
                  flagCol0 = true;
              }
          }
          for (int j = 0; j < cols; j++) {
              if (matrix[0][j] == 0) {
                  flagRow0 = true;
              }
          }
          for (int i = 1; i < rows; i++) {
              for (int j = 1; j < cols; j++) {
                  if (matrix[i][j] == 0) {
                      matrix[i][0] = matrix[0][j] = 0;
                  }
              }
          }
          for (int i = 1; i < rows; i++) {
              for (int j = 1; j < cols; j++) {
                  if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                      matrix[i][j] = 0;
                  }
              }
          }
          if (flagCol0) {
              for (int i = 0; i < rows; i++) {
                  matrix[i][0] = 0;
              }
          }
          if (flagRow0) {
              for (int j = 0; j < cols; j++) {
                  matrix[0][j] = 0;
              }
          }
      }
  }