Leetcode.73.Matrix Zeroes

题目

给定一个m*n的矩阵, 如果某个数为0, 则将该行和列都置为0.

Input: [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

思路1

最简单的方式, 先遍历, 将为0的行和列存在set中, 再将set中的行和列设置为0.

时间复制度O(m*n), 空间复杂度O(m+n)

void setZeroes(vector<vector<int>>& matrix) {
  // 找出为0的行和列
  int m = matrix.size();
  if (m == 0) {
      return;
  }
  int n = matrix[0].size();
  set<int> zeroRows;
  set<int> zeroCols;
  for (int i = 0;i < m; i++) {
      for (int j = 0;j < n; j++) {
          if(matrix[i][j] == 0) {
              zeroRows.insert(i);
              zeroCols.insert(j);
          }
      }
  }

  for (int i = 0;i < m; i++) {
      for (int j = 0;j < n; j++) {
          if(zeroRows.find(i) != zeroRows.end() || zeroCols.find(j) != zeroCols.end()) {
              matrix[i][j] = 0; 
          }
      }
  }
}

思路2

主要优化空间复杂度, 利用矩阵本身的第一行和第一列用于存储需要置为0的位置. 第一行和第一列的情况需要用其他参数记录.

时间复制度O(m*n), 空间复杂度O(1).

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size();
    if (m == 0) {
        return;
    }
    int n = matrix[0].size();
    int64_t rowZero = 0, colZero = 0;

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

总结

不止优化时间复杂度, 优化空间复杂度也很重要.

往往通过巧妙的办法记录空间, 比如位运算可以大大减少空间, 但位运算容易越界.