Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
題目沒有什麼難度,但是可以在空間復雜度上做一些處理:
開始寫的算法比較簡單,將行和列中為0的部分記錄下來,然後再經過一個賦值操作:
class Solution { public: void setZeroes(vector> &matrix) { if(matrix.empty()||matrix[0].empty()) { return; } int m = matrix.size(); int n = matrix[0].size(); vector row; vector col; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(matrix[i][j] == 0) { if(find(col.begin(),col.end(),j) == col.end()) { col.push_back(j); } if(find(row.begin(),row.end(),i) == row.end()) { row.push_back(i); } } } } for(int i = 0; i < row.size(); i++) { for(int j = 0; j < n; j++) { matrix[row[i]][j] = 0; } } for(int i = 0; i < m; i++) { for(int j = 0; j 還有一種比較好的做法就是利用已有的內存空間進行操作: 1 首先判斷第一行,第一列是否需要置0
2 利用第一行,和第一列,記錄當前位置如果為0,需要置0的行和列的位置,也就是利用第一行,第一列保存中間值
3 對應行,列置0
4 第一行,第一列進行處理:
void setZeroes(vector> &matrix) { // Start typing your C/C++ solution below // DO NOT write int main() function int row = matrix.size(); if(row == 0) return; int col = matrix[0].size(); if(col == 0) return; bool firstrowiszero = false; bool firstcoliszero = false; for(int j = 0; j < col; ++j) if(matrix[0][j] == 0){ firstrowiszero = true; break; } for(int i = 0; i < row; ++i) if(matrix[i][0] == 0){ firstcoliszero = true; break; } for(int i = 1; i < row; ++i) for(int j = 1; j < col; ++j){ if(matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } for(int i = 1; i < row; ++i) for(int j = 1; j < col; ++j) if(matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0; if(firstrowiszero){ for(int j = 0; j < col; ++j) matrix[0][j] = 0; } if(firstcoliszero){ for(int i = 0; i < row; ++i) matrix[i][0] = 0; } }