Set Matrix Zeroes

原題鏈接Set Matrix Zeroes

給定一個m × n矩陣，如果矩陣中某個元素是0，那么就將它所在的行，所在的列上的所有元素都變成0。要求空間復雜度在O(1)，也就是說在原矩陣上就修改

在原矩陣上做修改無非兩種方法

一種是使用遞歸，即發現某個元素是0，就把對應行對應列的每個元素賦值為0，然后遞歸的以它所在這一行，這一列的每個元素為起點，依次做同樣的事情

這種方法在遞歸的過程中極易出錯，而且對于很多邊界條件無法很好的控制

另外一種是先不著急對矩陣的元素進行更改，只記錄哪幾行，哪幾列的元素應該被賦值成0。不過需要在原矩陣上記錄，而不能使用額外的空間

這種方法唯一需要解決的就是如何記錄在原矩陣中。

---

綜上，可以看出使用第二種方法最為合適，但是，要怎么保存都有哪幾行，哪幾列的元素應該被置成0呢。試想，在遍歷完矩陣后，矩陣的某些位置應該是被改變的，這些被改變的位置標記著對應行，或者是對應列的所有元素是否應該被置成0。如果把行和列分開來記錄，那么可以說
應該有一行的元素記錄對應列是否被置為0，同時也應該有一列元素記錄對應行是否被置為1

那么，只需要將原矩陣中的某個行和某一列用來記錄就可以了，具體哪一行哪一列不固定，不過正常來說，選擇第0行記錄每一列是否應該被置為0，選擇第0列記錄每一行是否應該被置為0比較合適

那么，程序唯一需要做的就是遍歷一遍矩陣，如果某個元素值為0，就將第0行的對應列置為0，同時也要將第0列的對應行置為0。這樣，當遍歷結束后，只需要再遍歷一遍第0行，把是0的位置的那一列都變為0，同時遍歷一遍第0列，把是0的位置的那一行都變為0.

但是，有個問題！

如果遍歷的時候碰巧第0行的某個元素的值為0，那么按照上面的做法，應該是

將第0行的當前列（還是這個元素所在位置）置為0。這一步驟沒什么問題
將第0列的當前行（注意當前行是0）置為0，也就是將第0行第0列這個位置置為0

第二步會出現什么問題？倘若第0行第0列的那個位置被置為0，那么再更改矩陣元素時，第0行和第0列的所有元素將變為0，最終導致矩陣所有元素都變為0！

第0列的某個元素的值為0也是同理。

所以這種方法是不可取的，不過只是對于處理第0行和第0列的所有元素不可取，換句話說只是對第0行第0列的那個元素不可取（注意第0行和第0列與第0行第0列的區別）

那么程序無非要做的就是對上面問題單獨處理

只要是第0行的某個元素是0，那么就找個變量記錄第0行的所有元素應該都被置為0
只要是第0列的某個元素是0，那么就找個變量記錄第0列的所有元素應該都被置為0

當然，對于第0行和第0列的置0操作都應該被放在最后執行，也就是放在將矩陣元素都大體改完之后執行。不然，把第0行和第0列的所有元素都置為0了，那么如果再根據第0行和第0列判斷對應列和對應行是否應該被置為0，結果只會另矩陣所有元素都變為0

另外，上述操作只是為了防止將第0行第0列的那個位置的元素置為0。

代碼如下

class Solution { public:void setZeroes(vector<vector<int>>& matrix) {if(matrix.empty() || matrix[0].empty())return;/* 記錄第0行的元素是否應該被置為0 */bool oneRowZero = false;/* 記錄第0列的元素是否應該被置為0 */bool oneColumnZero = false;for(int i = 0; i < matrix.size(); ++i){for(int j = 0; j < matrix[i].size(); ++j){if(matrix[i][j] == 0){/* 如果某個元素是0，就將第0行的對應列，第0列的對應行置為0 */matrix[i][0] = matrix[0][j] = 0;/* 如果是第0行的元素是0，那么就任務第0行應該被置為0 */if(i == 0)oneRowZero = true;/* 同理第0列 */if(j == 0)oneColumnZero = true;} } } /* 遍歷矩陣第0列，如果第0列的某個元素是0，就將對應行的元素置0 *//* 這里沒有考慮第0行第0列 */for(int i = 1; i < matrix.size(); ++i){if(matrix[i][0] == 0){for(int j = 1; j < matrix[i].size(); ++j)matrix[i][j] = 0;}}/* 同理，遍歷矩陣第0行，將對應列元素置0 */for(int j = 1; j < matrix[0].size(); ++j){if(matrix[0][j] == 0){for(int i = 1; i < matrix.size(); ++i)matrix[i][j] = 0;}}/* 設置第0行 */if(oneRowZero){for(int j = 0; j < matrix[0].size(); ++j)matrix[0][j] = 0;}/* 設置第0列 */if(oneColumnZero){for(int i = 0; i < matrix.size(); ++i)matrix[i][0] = 0;}} }

本題要求空間復雜度在O(1)，所以不能重新開辟一塊矩陣作為更新后的值。只能想辦法在原矩陣上做修改，而對于遞歸而言，每次遞歸都要遞歸一整行和一整列，遞歸深度過深，容易出錯。那么就只能在原矩陣中找一些位置記錄都有哪幾行哪幾列應該被置為0，這個過程中需要考慮如果將第0行第0列那個位置置為0的話，會導致整個矩陣變為0，所以需要單獨考慮。

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----给定一个矩阵，如果某个元素是0，就将所在行所在列上所有元素否置0的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。