LeetCodeDay36 —— 矩阵置零★★☆

73. 矩阵置零

描述

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

思路

1. 时间复杂度O(mn),空间复杂度O(mn)的算法，复制一份Matrix，将0对应行列的元素置位0.
2. 时间复杂度O(mn),空间复杂度O(m + n)的算法，利用一个M大小和一个N大小的数组，保存0元素的小标，然后将对应行列的元素置位0.
3. 时间复杂度O(mn),空间复杂度O(1)的算法，利用首行首列的元素来表示该行该列是否有0元素，然后将对应行列的元素置位0.该方法需先统计首行首列自己是否有0元素，最后将首行首列置0.(参考)

Tips

1. 题目需要遍历每个元素，所以时间复杂度O(mn)是较难优化的，突破点在于空间复杂度。
2. 第一种解法直接复制了整个数组，仔细思考下其实只需保存0元素的小标即可，此时可将空间复杂度优化为O(m + n)
3. 进一步优化，要将空间复杂度降为O(1),则需利用数组本身来保存0的位置了。不难想到可以将上述额外的两个数组转换为首行首列，具体步骤如下：
   1)检查并记录第一行和第一列是否需要归零；
   2)遍历矩阵，一旦发现某个元素为0，则将它所在的行和列的第一个元素置为0;
   3)遍历第一行和第一列，如果是0，则将其对应的整个行或者整个列的元素置为0;
   4)如果第一行或者第一列需要归零，则将其归零。时间复杂度为O(m*n)，空间复杂度为O(1)。

class Solution_73_01 {
 public:
  void setZeroes(vector<vector<int>>& matrix) {
    vector<vector<int>> tmp = matrix;
    for (int i = 0; i < matrix.size(); ++i) {
      for (int j = 0; j < matrix[i].size(); ++j) {
        if (tmp[i][j] == 0) {
          for (int k = 0; k != matrix[i].size(); ++k) matrix[i][k] = 0;
          for (int k = 0; k != matrix.size(); ++k) matrix[k][j] = 0;
        }
      }
    }
  }
};

class Solution_73_02 {
 public:
  void setZeroes(vector<vector<int>>& matrix) {
    if (matrix.empty()) return;
    int hight = matrix.size(), width = matrix[0].size();
    vector<bool> row0, col0;
    row0.assign(hight, false);
    col0.assign(width, false);
    for (int i = 0; i < hight; ++i) {  //记录0点的位置
      for (int j = 0; j < width; ++j) {
        if (matrix[i][j] == 0) {
          row0[i] = true;
          col0[j] = true;
        }
      }
    }
    for (int i = 0; i < row0.size(); ++i) {
      if (!row0[i]) continue;
      for (int j = 0; j < width; ++j) {
        matrix[i][j] = 0;
      }
    }
    for (int i = 0; i < col0.size(); ++i) {
      if (!col0[i]) continue;
      for (int j = 0; j < hight; ++j) {
        matrix[j][i] = 0;
      }
    }
  }
};

class Solution_73_03 {
 public:
  void setZeroes(vector<vector<int>>& matrix) {
    if (matrix.empty()) return;
    int hight = matrix.size(), width = matrix[0].size();
    bool isHasZeroRow = false, isHasZeroCol = false;
    for (int i = 0; i < hight; ++i) {
      if (matrix[i][0] == 0) {
        isHasZeroRow = true;
        break;
      }
    }
    for (int i = 0; i < width; ++i) {
      if (matrix[0][i] == 0) {
        isHasZeroCol = true;
        break;
      }
    }
    // 将0元素所在行列的第一个元素置为0
    for(int i = 1; i < hight; ++i){
      for(int j = 1; j < width; ++j){
        if(matrix[i][j] == 0){
          matrix[i][0] = 0;
          matrix[0][j] = 0;
        }
      }
    }

    // 根据首行、首列将对应元素置0
    for(int row = 1; row < hight; ++row){
      if(matrix[row][0] == 0){
        for(int col = 1; col < width; ++col){
          matrix[row][col] = 0;
        }
      }
    }
    for(int col = 1; col < width; ++col){
      if(matrix[0][col] == 0){
        for(int row = 1; row < hight; ++row){
          matrix[row][col] = 0;
        }
      }
    }

    cout<< isHasZeroRow << " " << isHasZeroCol << endl;
    // 处理首行、首列
    if(isHasZeroRow){
      for(int i = 0; i < hight; ++i){
        matrix[i][0] = 0;
      }
    }
    if(isHasZeroCol){
      for(int i = 0; i < width; ++i){
        matrix[0][i] = 0;
      }
    }
  }
};