73. 矩陣置零

描述

• 給定一個(gè) m x n 的矩陣，如果一個(gè)元素為 0，則將其所在行和列的所有元素都設(shè)為 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]
    ]
進(jìn)階:
  一個(gè)直接的解決方案是使用  O(mn) 的額外空間，但這并不是一個(gè)好的解決方案。
  一個(gè)簡單的改進(jìn)方案是使用 O(m + n) 的額外空間，但這仍然不是最好的解決方案。
  你能想出一個(gè)常數(shù)空間的解決方案嗎？

思路

1. 時(shí)間復(fù)雜度O(mn),空間復(fù)雜度O(mn)的算法，復(fù)制一份Matrix，將0對應(yīng)行列的元素置位0.
2. 時(shí)間復(fù)雜度O(mn),空間復(fù)雜度O(m + n)的算法，利用一個(gè)M大小和一個(gè)N大小的數(shù)組，保存0元素的小標(biāo)，然后將對應(yīng)行列的元素置位0.
3. 時(shí)間復(fù)雜度O(mn),空間復(fù)雜度O(1)的算法，利用首行首列的元素來表示該行該列是否有0元素，然后將對應(yīng)行列的元素置位0.該方法需先統(tǒng)計(jì)首行首列自己是否有0元素，最后將首行首列置0.(參考)

Tips

1. 題目需要遍歷每個(gè)元素，所以時(shí)間復(fù)雜度O(mn)是較難優(yōu)化的，突破點(diǎn)在于空間復(fù)雜度。
2. 第一種解法直接復(fù)制了整個(gè)數(shù)組，仔細(xì)思考下其實(shí)只需保存0元素的小標(biāo)即可，此時(shí)可將空間復(fù)雜度優(yōu)化為O(m + n)
3. 進(jìn)一步優(yōu)化，要將空間復(fù)雜度降為O(1),則需利用數(shù)組本身來保存0的位置了。不難想到可以將上述額外的兩個(gè)數(shù)組轉(zhuǎn)換為首行首列，具體步驟如下：
   1)檢查并記錄第一行和第一列是否需要?dú)w零；
   2)遍歷矩陣，一旦發(fā)現(xiàn)某個(gè)元素為0，則將它所在的行和列的第一個(gè)元素置為0;
   3)遍歷第一行和第一列，如果是0，則將其對應(yīng)的整個(gè)行或者整個(gè)列的元素置為0;
   4)如果第一行或者第一列需要?dú)w零，則將其歸零。時(shí)間復(fù)雜度為O(m*n)，空間復(fù)雜度為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點(diǎn)的位置
      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元素所在行列的第一個(gè)元素置為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;
        }
      }
    }

    // 根據(jù)首行、首列將對應(yīng)元素置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;
      }
    }
  }
};