給定一個?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]]

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

進階：

• 一個直觀的解決方案是使用 ?O(mn)?的額外空間，但這并不是一個好的解決方案。（查找到一個就遍歷一次行和列）
• 使用O(m+n）的方法，如下：

思路：使用兩個標記數組（哈希表記錄）row,col分別記錄二維矩陣中值為零的元素所在的行列值。再遍歷一遍矩陣，判斷當前元素值是否位于被標記的行或列上，位于則直接值為零。

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {map<int,int>row,col;for(int i=0;i<matrix.size();i++){//rowvector<int>a;a=matrix[i];for(int j=0;j<a.size();j++){//columnif(a[j]==0){row[i]=1;col[j]=1;}}}for(int i=0;i<matrix.size();i++){vector<int>a;a=matrix[i];for(int j=0;j<a.size();j++){if(row[i]==1||col[j]==1){//位于有0的行或列的數，所以值為零matrix[i][j]=0;}}}}
};

• 一個簡單的改進方案是使用?O(m?+?n)?的額外空間，但這仍然不是最好的解決方案。（注意時間復雜度仍然是O(m*n)）,空間復雜度由O(m+n)降低到O（1）);
• 你能想出一個僅使用常量空間的解決方案嗎？

用矩陣的第一行和第一列代替方法一中的兩個標記數組，以達到 O(1)的額外空間。但這樣會導致原數組的第一行和第一列被修改，無法記錄它們是否原本包含 0。因此我們需要額外使用兩個標記變量分別記錄第一行和第一列是否原本包含 0。

在實際代碼中，我們首先預處理出兩個標記變量，接著使用其他行與列去處理第一行與第一列，然后反過來使用第一行與第一列去更新其他行與列，最后使用兩個標記變量更新第一行與第一列即可。

注意，在使用第一行和第一列記錄其他位置是否存在值為零的元素時，若存在應該將第一行和第一列對應的值置為零，（若第一行中存在零，則對應的這一列也要值為零，所以也會被標記，若第一行不存在零也不會導致影響第一行原本存在的值）。

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {//首先，使用兩個變量分別記錄第一行和第一列是否存在值為零的元素int a=0,b=0;vector<int>row;row=matrix[0];for(int i=0;i<row.size();i++){//第一列if(row[i]==0){a=1;break;}}for(int i=0;i<matrix.size();i++){//第一行if(matrix[i][0]==0){b=1;break;}}//使用第一行和第一列分別記錄其他數組中for(int i=1;i<matrix.size();i++){//行vector<int>c;c=matrix[i];for(int j=1;j<c.size();j++){//列if(matrix[i][j]==0){matrix[0][j]=0;//行matrix[i][0]=0;//列}}}//遍歷一遍，判斷第一行第一列以外的元素是否需要置零for(int i=1;i<matrix.size();i++){vector<int>c;c=matrix[i];for(int j=1;j<c.size();j++){if(matrix[i][0]==0 || matrix[0][j]==0){matrix[i][j]=0;//注意寫成==導致錯誤}}}if(a==1){for(int i=0;i<row.size();i++){matrix[0][i]=0;}}if(b==1){for(int j=0;j<matrix.size();j++){matrix[j][0]=0;}}}
};