LeetCode 73 _ Set Matrix Zeroes 给矩阵赋值0

佚名 6年前 (2019-04-11) 随笔 1160人围观抢沙发百度已收录

Description:

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

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?

Solution:

Code:

public void setZeroes(int[][] matrix) {
    int row = matrix.length, col = matrix[0].length;
    int overlap1 = 1;
    for (int i = 0; i < row; i++){
        if (matrix[i][0] == 0){
            overlap1 = 0;  // 记录第0列是否存在零,因为(0,0)位需要存放第0行
        }
        for (int j = 1; j < col; j++){
            if (matrix[i][j] == 0){
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }               
    }

   for (int i = row-1; i >= 0; i--){  // 从后开始,因为第一排是判断的前提,先改会影响到后面的判断
        for (int j = col-1; j > 0 ; j--){
            if (matrix[i][0] == 0 || matrix[0][j] == 0){
                matrix[i][j] = 0;
            }
        }
        if (overlap1 == 0){
            matrix[i][0] = 0;
        }
    }
}

提交情况:

这个Memory Usage有点迷，我最开始测出来都是5%左右，试了多个标答都是这个结果。于是加上了0的判断，升到了57%，正当我惊叹边界对效率的提高时，我删去了边界判断，效率却变成了70%+……尽管一直知道这个值在浮动，但这个变化也太大，着实看不懂……_(:зゝ∠)_

Runtime: 1 ms, faster than 94.83% of Java online submissions for Set Matrix Zeroes.

Memory Usage: 50.5 MB, less than 5.10% of Java online submissions for Set Matrix Zeroes.

Memory Usage: 45.2 MB, less than 57.82% of Java online submissions for Set Matrix Zeroes.

Memory Usage: 44.2 MB, less than 71.94% of Java online submissions for Set Matrix Zeroes.