0073. Set Matrix Zeroes - kumaeki/LeetCode GitHub Wiki

0073. Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's, and return the matrix.

You must do it in place.

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]

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

Example 2:

Input: matrix = [[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]]

Constraints:

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1

Follow up:

A straightforward 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?

解法1

乍一看不可能.其实, 只要思想不滑坡, 方法总比问题多.

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean flgFirstCol = false, flgFirstRow = false;

        // 判断第一列是否有0, 如果有, flg设置为true
        for(int i = 0; i < m; i++)
            if(matrix[i][0] == 0){
                flgFirstCol = true;
                break;
            }
        
        // 判断第一行是否有0,如果, 那么把最左上角设为0
        for(int j = 0; j < n; j++)
            if(matrix[0][j] == 0){
                flgFirstRow = true;
                break;
            }
        
        // 从第二行第二列开始遍历二位数组, 如果有0, 那么把该位置对应的行和列的第一个元素设置为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;
                }
        
        // 从第二行开始, 如果第一个元素为0, 那么整行设置为0
        for(int i = 1; i < m; i++)
            if(matrix[i][0] == 0)
                matrix[i] = new int[n];
        
        // 从第二列开始, 如果第一个元素为0, 把整列设置为0
        for(int j = 1; j < n; j++)
            if(matrix[0][j] == 0)
                for(int i = 1; i < m; i++)
                    matrix[i][j] = 0;
        
        // 如果flgFirstRow为真, 那么第一行全部设置为0
        if(flgFirstRow)
            matrix[0] = new int[n];
        
        // 如果flgFirstCol为真, 那么把第一列全部设置为0
        if(flgFirstCol)
            for(int i = 0; i < m; i++)
                matrix[i][0] = 0;
    }
}
⚠️ **GitHub.com Fallback** ⚠️