## 一.題目描述 Given a?`m*n`?matrix, if an element is?`0`, set its entire row and column to?`0`. Do it in place.? Follow up: Did you use extra space?? A straight forward solution using?`O(mn)`?space is probably a bad idea.? A simple improvement uses?`O(m + n)`?space, but still not the best solution.? Could you devise a constant space solution? ## 二.題目分析 該題目最直觀的解法就是開辟一個新的矩陣，當原矩陣存在零元素的時候，就將新矩陣的對應行和列置為零。這樣空間復雜度較高，也是題目不允許的。 若要做到空間復雜度為常數，我的做法是就是利用矩陣的第一行和第一列來作為標記使用，這樣便不用開辟新的存儲空間。具體方法： 1. 先確定第一行和第一列是否需要清零，即：遍歷第一行中是否有`0`，也同時記下第一列中有沒有`0`。在以下代碼中，使用bool型變量`x_key`和`y_key`分別記錄第一行和第一列的情況； 2. 掃描剩下的矩陣元素，如果遇到了`0`，就將該元素所對應的第一行和第一列上的元素賦值為`0`； 3. 在遍歷完二維數組后，就可以根據第一行和第一列的信息，將剩下的矩陣元素進行賦值。拿第一行為例，如果掃描到第`i`個元素為`0`，就將二維數組的第`i`列全部置`0`； 4. 最后，根據1中bool型變量`x_key`和`y_key`的值，處理第一行和第一列。如果最開始得到的第一行中有`0`的話，就整行清零，對第一列也采取同樣的處理。 ## 三.示例代碼 第一種方法如下： ~~~ #include <vector> using namespace std; class Solution { public: // 時間復雜度O(m * n)，空間復雜度O(m + n) void setZeros(vector<vector<int> >& matrix) { const size_t x = matrix.size(); const size_t y = matrix[0].size(); if (x == 0 || y == 0) return; vector<bool> rowRes(x, false); vector<bool> colRes(y, false); for (size_t i = 0; i < x; i++) { for (size_t j = 0; j < y; j++) { if (matrix[i][j] == 0) rowRes[i] = colRes[j] = true; } } // set zero for (size_t i = 0; i < x; i++) { if (rowRes[i]) for (size_t k = 0; k < x; k++) matrix[i][k] = 0; } for (size_t j = 0; j < y; j++) { if (colRes[j]) for (size_t k = 0; k < x; k++) matrix[k][j] = 0; } } }; ~~~ 以上方法的空間復雜度為`O(m + n)`，并不能達到題目要求的最終要求。 **第二種方法**如下： ~~~ #include <vector> using namespace std; class Solution { public: void setZerosBetter(vector<vector<int> >& matrix) { const size_t x = matrix.size(); const size_t y = matrix[0].size(); bool x_key = false, y_key = false; if (x == 0 || y == 0) return; for (size_t i = 0; i < y; i++) { if (matrix[0][i] == 0) { x_key = true; break; } } for (size_t i = 0; i < x; i++) { if (matrix[i][0] == 0) { y_key = true; break; } } for (size_t i = 0; i < x; i++) { for (size_t j = 0; j < y; j++) { if (matrix[i][j] == 0 && i > 0 && j > 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } // 調整1~x行、1~y列的元素 for (size_t i = 1; i < x; i++) if (matrix[i][0] == 0) { for (size_t k = 1; k < y; k++) matrix[i][k] = 0; } for (size_t j = 1; j < y; j++) if (matrix[0][j] == 0) { for (size_t k = 1; k < x; k++) matrix[k][j] = 0; } // 最后調整第一行第一列 if (y_key) for (size_t k = 0; k < x; k++) matrix[k][0] = 0; if (x_key) for (size_t k = 0; k < y; k++) matrix[0][k] = 0; } }; ~~~  ## 四.小結 這道題如果只是僅僅想實現功能的話，不需要什么技巧，只有提高對空間復雜度的要求才能體現出算法設計的思想。