首页 > 代码库 > 【LeetCode】Set Matrix Zeroes (2 solutions)
【LeetCode】Set Matrix Zeroes (2 solutions)
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?
解法一：
使用数组分别记录需要置零的行列。然后根据数组信息对相应行列置零。
空间复杂度O(m+n)
class Solution {public: void setZeroes(vector<vector<int> > &matrix) { if(matrix.empty() || matrix[0].empty()) return; int m = matrix.size(); int n = matrix[0].size(); vector<bool> row(m, false); vector<bool> col(n, false); for(int i = 0; i < m; i ++) { for(int j = 0; j < n; j ++) { if(matrix[i][j] == 0) { row[i] = true; col[j] = true; } } } for(int i = 0; i < m; i ++) { for(int j = 0; j < n; j ++) { if(row[i] == true) matrix[i][j] = 0; if(col[j] == true) matrix[i][j] = 0; } } }};
解法二：
使用第一行和第一列记录该行和该列是否应该置零。
对于由此覆盖掉的原本信息，只要单独遍历第一行第一列判断是否需要置零即可。
空间复杂度O(1)
class Solution {public: void setZeroes(vector<vector<int> > &matrix) { if(matrix.empty() || matrix[0].empty()) return; int m = matrix.size(); int n = matrix[0].size(); bool firstRow = false; bool firstCol = false; for(int i = 0; i < m; i ++) { if(matrix[i][0] == 0) { firstCol = true; break; } } for(int j = 0; j < n; j ++) { if(matrix[0][j] == 0) { firstRow = true; break; } } for(int i = 1; i < m; i ++) { for(int j = 1; j < n; j ++) { if(matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } //set zero for(int i = 1; i < m; i ++) { for(int j = 1; j < n; j ++) { if(matrix[i][0] == 0) matrix[i][j] = 0; if(matrix[0][j] == 0) matrix[i][j] = 0; } } if(firstRow == true) { for(int j = 0; j < n; j ++) { matrix[0][j] = 0; } } if(firstCol == true) { for(int i = 0; i < m; i ++) { matrix[i][0] = 0; } } }};
【LeetCode】Set Matrix Zeroes (2 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。