【Leetcode每日一题】2022-09-30 面试题 01.08 零矩阵 Java实现

---

题目

方案一 我的思路：两个HashSet

遍历二维数组，用两个hashSet来存储0出现的行和列

在遍历完二维数组以后，再按行、按列将对应的行和列全部赋值为0

import java.util.Arrays;
import java.util.HashSet;

class Solution {
    public void setZeroes(int[][] matrix) {

        HashSet<Integer> rowSet = new HashSet<>();
        HashSet<Integer> colSet = new HashSet<>();

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    rowSet.add(i);
                    colSet.add(j);
                }
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            if (rowSet.contains(i)) {
                Arrays.fill(matrix[i], 0);
            }
        }

        for (int j = 0; j < matrix[0].length; j++) {
            if (colSet.contains(j)) {
                for (int i = 0; i < matrix.length; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

方案二 标记数组

和上面的思路是一样的，用两个标记数组分别记录每一行和每一列是否有0出现

具体做法是，首先遍历数组一次，如果某个元素是0，那么就将该元素所在的行和列所对应的标记数组的位置设置为true。最后再次遍历该数组，根据标记数组中记录的位置，更新原数组中的数。

只不过将HashSet替换成了数组，不过，如果矩阵中的0的个数特别少，会造成空间上的浪费吧。

import java.util.Arrays;

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;

        boolean[] visRow = new boolean[row];
        boolean[] visCol = new boolean[col];

        Arrays.fill(visRow, false);
        Arrays.fill(visCol, false);

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    visRow[i] = true;
                    visCol[j] = true;
                }
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (visRow[i] || visCol[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

方案三 使用两个标记变量

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

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

import java.util.Arrays;

class Solution {
    public void setZeroes(int[][] matrix) {

        boolean isFirstRowContainZeros = false;
        boolean isFirstColumnContainZeros = false;

        //判断matrix矩阵的第一行是否有零
        for (int i = 0; i < matrix[0].length; i++) {
            if (matrix[0][i] == 0) {
                isFirstRowContainZeros = true;
                break;
            }
        }

        //判断matrix矩阵的第一列是否有零
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                isFirstColumnContainZeros = true;
                break;
            }
        }

        //处理矩阵中的非第一行、非第一列的元素
        //如果遇到0，比如在matrix[2][3]的位置是0，那么则把matrix[0][3]和matrix[2][0]的位置修改为0
        //意味着，之后，第三列和第二行都是零
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        //如果matrix矩阵的第一行有0
        if (isFirstRowContainZeros) {
            Arrays.fill(matrix[0], 0);
        }

        //如果matrix矩阵的第一列有0
        if (isFirstColumnContainZeros) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}