首页 > 代码库 > 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.
思路：使用两个向量分别记录每一行和每一列是否存在0。
1 class Solution { 2 public: 3 void setZeroes( vector<vector<int>> &matrix ) { 4 int rows = matrix.size(), cols = matrix[0].size(); 5 vector<bool> rowFlag( rows, false ), colFlag( cols, false ); 6 for( int i = 0; i < rows; ++i ) { 7 for( int j = 0; j < cols; ++j ) { 8 if( matrix[i][j] == 0 ) { 9 rowFlag[i] = colFlag[j] = true;10 }11 }12 }13 for( int i = 0; i < rows; ++i ) {14 for( int j = 0; j < cols; ++j ) {15 if( rowFlag[i] || colFlag[j] ) {16 matrix[i][j] = 0;17 }18 }19 }20 return;21 }22 };
fellow up要求常空间复杂度。显然，我们应该考虑利用数组本身来记录某行某列是否存在0。若某一行（或某一列）存在0，则该行（或该列）的第一个元素也必将被置为0。因此，我们可以使用数组的第一行和第一列来分别记录矩阵剩余部分的每一行和每一列是否存在0。同时，我们还需要两个标记来记录第一行和第一列是否本身就存在0。
1 class Solution { 2 public: 3 void setZeroes( vector<vector<int>> &matrix ) { 4 if( matrix.empty() || matrix[0].empty() ) { return; } 5 int rows = matrix.size(), cols = matrix[0].size(); 6 bool rowFlag = false, colFlag = false; 7 // 检查第一列 8 for( int i = 0; i < rows; ++i ) { 9 if( matrix[i][0] == 0 ) { colFlag = true; break; }10 }11 // 检查第一行12 for( int j = 0; j < cols; ++j ) {13 if( matrix[0][j] == 0 ) { rowFlag = true; break; }14 }15 // 检查矩阵的剩余部分16 for( int i = 1; i < rows; ++i ) {17 for( int j = 1; j < cols; ++j ) {18 if( matrix[i][j] == 0 ) { matrix[i][0] = matrix[0][j] = 0; }19 }20 }21 // 置位矩阵的剩余部分22 for( int i = 1; i < rows; ++i ) {23 for( int j = 1; j < cols; ++j ) {24 if( matrix[i][0] == 0 || matrix[0][j] == 0 ) { matrix[i][j] = 0; }25 }26 }27 // 置位第一行28 if( rowFlag ) {29 for( int j = 0; j < cols; ++j ) { matrix[0][j] = 0; }30 }31 // 置位第一列32 if( colFlag ) {33 for( int i = 0; i < rows; ++i ) { matrix[i][0] = 0; }34 }35 return;36 }37 };
Set Matrix Zeroes
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。