leetcode--Set Matrix Zeroes

妖狐艹你老母 2021-10-19 11:07 148阅读 0赞

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(*m**n*) 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?

public class Solution {
    	/**The algorithm is simple. but we need to pay attention to the first row and first column.
         * @author Averill Zheng
         * @version 2014-06-15
         * @since JDK 1.7
         */ 
    	public void setZeroes(int[][] matrix) {
    		int row = matrix.length;
    		if(row > 0){
    			int column = matrix[0].length;
    			//find if we need to set first row or first column to be zero
    			boolean setRow = false;
    			boolean setColumn = false;
    			for(int i = 0; i < column; ++i){
    				if(matrix[0][i] == 0){
    					setRow = true; 
    					break;
    				}
    			}
    			for(int i = 0; i < row; ++i){
    				if(matrix[i][0] == 0){
    					setColumn = true;
    					break;
    				}
    			}
    			
    			for(int i = 1; i < row; ++i){
    				for(int j = 1; j < column; ++j){
    					if(matrix[i][j] == 0){
    						matrix[i][0] = 0;
    						matrix[0][j] = 0;
    					}
    				}
    			}
    			
    			//set zeros;
    			for(int j = 1; j < column; ++j){
    				if(matrix[0][j] == 0){
    					for(int i = 1; i < row; ++i)
    						matrix[i][j] = 0;
    				}
    			}
    			
    			for(int i = 1; i < row; ++i){
    				if(matrix[i][0] == 0){
    					for(int j = 1; j < column; ++j)
    						matrix[i][j] = 0;
    				}
    			}
    			if(setRow){
    				for(int i = 0; i < column; ++i)
    					matrix[0][i] = 0;
    			}
    			
    			if(setColumn){
    				for(int i = 0; i < row; ++i)
    					matrix[i][0] = 0;
    			}
    		}
        }
    }

转载于:https://www.cnblogs.com/averillzheng/p/3790281.html

[click to show follow up.]: https://oj.leetcode.com/problems/set-matrix-zeroes/