LeetCode Set Matrix Zeroes

73. 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后,它便不能再进行比较。充分理解题意后开始解题,使用第0行和第0列存储哪行哪列有0.将置0分为两部分,一部分为从matrix[1][1]开始到matrix[m][n],若matrix[i][j] = 0,则令matrix[i][0] = 0,matrix[0][j] = 0,即将其拆分,分别放在其第i行0列和第0行j列的位置,之后遍历置0。第二部分遍历第0行和第0列,若其中有一个为0,相对应的第0行或第0列置0。使用该方法空间复杂度为O(1),即只需存储变量row和col。

public class Solution {
    public void setZeroes(int[][] matrix) {
       //行
       int m = matrix.length;
       //列
       int n = matrix[0].length;
       //用第一行和第一列来存储哪行哪列有0
       boolean row = false;
       boolean col = false;

       for(int i = 0; i < m; i++){
           if(matrix[i][0] == 0){
               row = true;
               break;
           }
       }

       for(int j = 0; j < n; j++){
           if(matrix[0][j] == 0){
               col = true;
               break;
           }
       }
       //从第一行和第一列开始,若某行某列为0,标记
       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;
               }
           }
       }
       //从第一行开始遍历,若第i行第0列为0,则第i行都为0
       for(int i = 1; i < m; i++){
           if(matrix[i][0] == 0){
               for(int j = 1; j < n; j++){
                   matrix[i][j] = 0;
               }
           }
       }
       //从第1行第j列开始遍历,若第0行第j列为0,则第i行第j列为0
       for(int j = 1; j < n; j++){
           if(matrix[0][j] == 0){
               for(int i = 1; i < m; i++ ){
                   matrix[i][j] = 0;
               }
           }
       }
       //若第0-i行有0,则第i行第0列为0
       if(row == true){
           for(int i = 0; i < m; i++){
               matrix[i][0] = 0;
           }
       }
       //若第0-i列有0,则第0行第j列为0
       if(col == true){
           for(int j = 0; j < n; j++){
               matrix[0][j] = 0;
           }
       }
    }
}
Share