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?

解题思路：

这道题的题意是，对于矩阵matrix，若matrix[i][j]=0，那么将该行该列都置为0。注意更改后的0不作为0的判别标准。

因此，我们需要记录所有需要清零的行列。

题目要求空间复杂度为O(1)。

解法1：我们先不考虑空间复杂度的情况，用两个set分别记录需要清零的行和列，则有：

class Solution {
public:
    void setZeroes(vector>& matrix) {
        int m = matrix.size();
        if(m==0){
            return;
        }
        int n = matrix[0].size();
        if(n==0){
            return;
        }
        set zeroRow;
        set zeroCol;
        for(int i=0; i::iterator it = zeroRow.begin(); it!=zeroRow.end(); it++){
            for(int i=0; i::iterator it = zeroCol.begin(); it!=zeroCol.end(); it++){
            for(int i=0; i
解法2：其实我们可以用两个bool数组来记录，对上述代码稍作修改，得到：
class Solution {
public:
    void setZeroes(vector>& matrix) {
        int m = matrix.size();
        if(m==0){
            return;
        }
        int n = matrix[0].size();
        if(n==0){
            return;
        }
        vector row(m, false);
        vector col(n, false);
        for(int i=0; i
解法3：上述两种方法的空间复杂度为O(m+n)。要达到O(1)的空间要求，需要充分利用已有空间。可以将标记记录在第一行和第一列中。但是首先需要两个布尔值记录第一行和第一列是否需要清零。代码如下：
class Solution {
public:
    void setZeroes(vector>& matrix) {
        int m = matrix.size();
        if(m==0){
            return;
        }
        int n = matrix[0].size();
        if(n==0){
            return;
        }
        bool firstRow = false, firstCol = false;    //第一行和第一列是否需要置为0
        for(int i=0; i

 
转载请注明： » [LeetCode] Set Matrix Zeroes

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->