面试金典0108 零矩阵

题目：

• 编写一种算法，若M × N矩阵中某个元素为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]
  ]

解题方法：

读到零直接修改行列这种做法会是数据变脏，导致结果不符合预期，因此需要将有0的行和列存下来，然后再想办法置零，这里有两种置零策略，前者时间复杂度更低，后者find()函数的复杂度为\(O(n)\)

1. 使用标记数组：遍历矩阵，找到有零存在的所有行和列；分别遍历这些行和列，并置零

   时间复杂度为\(O(n^2)\)，额外的空间复杂度为\(O(n)\)

2. 使用标记数组：遍历矩阵，找到有零存在的所有行和列；重新遍历矩阵，判断当前所在的行列是否属于有零存在的行列，因为用set集合存储了为零的行列，因此利用find()函数即可

   时间复杂度为\(O(n^3)\)，因为find()函数的复杂度为\(O(n)\)，额外的空间复杂度为\(O(n)\)

3. 使用两个标记变量：用矩阵的第一行和第一列来当标记数组，然后用两个标记变量标记原本第一行和第一列是否出现过0，这样就可以降低空间复杂度了！目前未实现

   时间复杂度为\(O(n^3)\)，额外的空间复杂度为\(O(1)\)

解法一：使用标记数组

• 集合的定义：set<int> set_row;

• 集合添加元素：

  • set_row.insert(int i);
  • 添加pair：set<pair<T1, T2>> set_pair; set_pair.emplace(T1 a, T2, b);

• 集合删除元素：成员函数 clear() 会删除 set 的所有元素。成员函数 erase() 会删除迭代器指定位置的元素或与对象匹配的元素。

  • set_row.erase(int a);删除对应的元素，如果没有会返回什么？
  • set_row.erase(iterator);删除迭代器位置元素
  • set_row.clear();删除全部元素

• 集合的遍历（只能用iterator）：

  set<int>::iterator it;
  for(it = set_row.begin(); it != set_row.end(); ++it)
  {
      cout << *it << endl; // *it为取it地址下的值
  }

• 查找元素是否在集合中：if(set_row.find(int a) != set_row.end()) return true; find的复杂度为\(O(n)\)，底层逻辑就是遍历整个set，直到end()

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        set<int> set_row, set_col;
        for(int i=0; i<matrix.size(); ++i)
        {
            for(int j=0; j<matrix[i].size(); ++j)
            {
                if(matrix[i][j] == 0)
                {
                    set_row.insert(i);
                    set_col.insert(j);
                }
            }
        }
        set<int>::iterator it;
        // set all the 0 rows
        for(it = set_row.begin(); it!=set_row.end(); ++it)
        {
            for(int j=0; j<matrix[*it].size(); ++j)
            {
                matrix[*it][j] = 0;
            }
        }

        // set all the 0 colums
        for(it = set_col.begin(); it!=set_col.end(); ++it)
        {
            for(int i=0; i<matrix.size(); ++i)
            {
                matrix[i][*it] = 0;
            }
        }
    }
};

解法二：使用标记数组

• 集合的find操作，见上文

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        set<int> set_row, set_col;
        for(int i=0; i<matrix.size(); ++i)
        {
            for(int j=0; j<matrix[i].size(); ++j)
            {
                if(matrix[i][j] == 0)
                {
                    set_row.insert(i);
                    set_col.insert(j);
                }
            }
        }
        for(int i=0; i<matrix.size(); ++i)
        {
            for(int j=0; j<matrix[i].size(); ++j)
            {
                if(set_row.find(i) != set_row.end()) // 时间复杂度O(n)
                {
                    matrix[i][j] = 0;
                }
                if(set_col.find(j) != set_col.end())
                {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};

解法三：使用两个标记变量（未实现）