01.08 零矩阵

1、题目

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

1）示例1

输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]

2）示例2

输入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

2、初步作答

2.1 思路

• 查找二维数组中为 0 的行号与列号
• 根据记录的行号与列号，修改二维数组

2.2 做法

• 建立两个长度分别为 M 和 N 的一维数组
• 遍历二维数组，记录为 0 的数组的行号（M数组对应下标加一）和列号（N数组对应下标加一）

2.3 代码

import java.util.Scanner;

public class Zeros {
    public static void main(String[] agrs){
        Scanner input = new Scanner(System.in);
        int r = input.nextInt();
        int l = input.nextInt();
        int[][] matrix = new int[r][l];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < l; j++) {
                matrix[i][j] = input.nextInt();
            }
        }
        Zeros.setZeroes(matrix);
        for (int i = 0; i < r; i++) {
            System.out.print("[");
            for (int j = 0; j < l; j++) {
                System.out.print(matrix[i][j]+"\t");
            }
            System.out.println("]");
        }
        input.close();
    }

    public static void setZeroes(int[][] matrix) {
        int[] row = new int[matrix.length];
        int[] line = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == 0){
                    row[i] = 1;
                    line[j] = 1;
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(row[i] == 1){
                    matrix[i][j] = 0;
                }
                if(line[j] == 1){
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：42.6 MB, 在所有 Java 提交中击败了19.80%的用户

通过测试用例：159 / 159

2.4 思考

• 前两天参加了字节的模拟笔试，感觉力扣的核心代码模式不太够。所以这里附的代码是采用牛客的ACM代码模式。

3、其余解法

3.1 使用两个标记变量

• 我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1)O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 00。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 00。

• 在实际代码中，我们首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false, flagRow0 = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flagCol0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                flagRow0 = true;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (flagCol0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flagRow0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
}