首页 > 代码库 > Set Matrix Zeroes
Set Matrix Zeroes
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?
方法一：扫到每个0元素，将其所在行和列中非0元素置为INF，最后在扫一遍，将所有INF的元素置0
1 class Solution { 2 public: 3 void setZeroes(vector<vector<int> > &matrix) { 4 for(int i=0; i<matrix.size(); ++i) //将0元素所在行和列的非0元素置为INF 5 for(int j=0; j<matrix[i].size(); ++j) 6 if( !matrix[i][j] ) setINF(matrix, i, j); 7 for(int i=0; i<matrix.size(); ++i) //将所有INF元素置为0 8 for(int j=0; j<matrix[i].size(); ++j) 9 if( matrix[i][j] == INF ) matrix[i][j] = 0;10 }11 12 void setINF(vector<vector<int> > &matrix, int x, int y) {13 for(int i=0; i<matrix.size(); ++i)14 if( matrix[i][y] ) matrix[i][y] = INF;15 for(int i=0; i<matrix[x].size(); ++i)16 if( matrix[x][i] ) matrix[x][i] = INF;17 }18 19 private:20 static const int INF = 0x3fffffff;21 };
方法二：利用第一行和第一列标记哪行和哪列全部置0，需要注意，第一行和第一列需要额外标记
1 class Solution { 2 public: 3 void setZeroes(vector<vector<int> > &matrix) { 4 bool frow = false, fcol = false; 5 for(int i=0; i<matrix[0].size(); ++i) //判断第一行是否需要清0 6 if( !matrix[0][i] ) { 7 frow = true; 8 break; 9 }10 for(int i=0; i<matrix.size(); ++i) //判断第一列是否需要清011 if( !matrix[i][0] ) {12 fcol = true;13 break;14 }15 for(int i=1; i<matrix.size(); ++i)16 for(int j=1; j<matrix[i].size(); ++j)17 if( !matrix[i][j] ) { //当前元素所在行和所在列，第一行和第一列对应的元素置0，作为标记18 matrix[i][0] = matrix[0][j] = 0;19 }20 for(int i=1; i<matrix.size(); ++i)21 for(int j=1; j<matrix[i].size(); ++j)22 if( !matrix[i][0] || !matrix[0][j] ) matrix[i][j] = 0; //按照标记来给对应的行和列置023 if( frow )24 for(int i=0; i<matrix[0].size(); ++i) matrix[0][i] = 0;25 if( fcol )26 for(int i=0; i<matrix.size(); ++i) matrix[i][0] = 0;27 }28 };
Set Matrix Zeroes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。