一.题目描述
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?
二.题目分析
该题目最直观的解法就是开辟一个新的矩阵，当原矩阵存在零元素的时候，就将新矩阵的对应行和列置为零。这样空间复杂度较高，也是题目不允许的。
若要做到空间复杂度为常数，我的做法是就是利用矩阵的第一行和第一列来作为标记使用，这样便不用开辟新的存储空间。具体方法：
三.示例代码
第一种方法如下：
;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 zerofor (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)，并不能达到题目要求的最终要求。
第二种方法如下：
;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;}};
四.小结
这道题如果只是仅仅想实现功能的话，不需要什么技巧，只有提高对空间复杂度的要求才能体现出算法设计的思想。
，学习不是人生的全部，但学习都征服不了，那我还能做什么?
