首页 > 代码库 > Set Matrix Zeros ****
Set Matrix Zeros ****
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
click to show follow up.
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?
Analyse: O(m + n) space
1 class Solution { 2 public: 3 void setZeroes(vector<vector<int>>& matrix) { 4 if (matrix.empty() || matrix[0].empty()) return; 5 // bool: rows[] stores the rows needed to be replaced by 0 6 // bool: cols[] stores the cols needed to be replaced by 0 7 int m = matrix.size(), n = matrix[0].size(); 8 vector<int> rows(m, false); 9 vector<int> cols(n, false);10 for (int i = 0; i < m; i++) {11 for (int j = 0; j < n; j++) {12 if (!matrix[i][j]) {13 rows[i] = true;14 cols[j] = true;15 }16 }17 }18 19 // replace the matrix accordingly20 for (int i = 0; i < m; i++) {21 if (rows[i]) {22 for (int j = 0; j < n; j++)23 matrix[i][j] = 0;24 }25 }26 for (int j = 0; j < n; j++) {27 if (cols[j]) {28 for (int i = 0; i < m; i++)29 matrix[i][j] = 0;30 }31 }32 }33 };
Analyse: O(1) space.
-- Scan the matrix, when it comes to 0, set all 1 in its row and column as 2. Scan the matrix again, replace all 2 with 0. However, we may encounter the situation where 2 has already been used in the matrix...
-- Use the first row and first column to store the information. Solution should be as the same. A very smart solution can be viewed at:
1 class Solution { 2 public: 3 void setZeroes(vector<vector<int> > &matrix) { 4 int col0 = 1, rows = matrix.size(), cols = matrix[0].size(); 5 6 for (int i = 0; i < rows; i++) { 7 if (matrix[i][0] == 0) col0 = 0; 8 for (int j = 1; j < cols; j++) 9 if (matrix[i][j] == 0)10 matrix[i][0] = matrix[0][j] = 0;11 }12 13 for (int i = rows - 1; i >= 0; i--) {14 for (int j = cols - 1; j >= 1; j--)15 if (matrix[i][0] == 0 || matrix[0][j] == 0)16 matrix[i][j] = 0;17 if (col0 == 0) matrix[i][0] = 0;18 }19 }20 };
Set Matrix Zeros ****
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。