526互联

Leetcode—矩阵置零

发布时间 2023-12-22 13:07:30作者: 吧拉吧拉吧

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：

输入：

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

示例 2：

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

方法1

  • 分析：根据题目所描述，我们可以先遍历数组找出所有0所在的位置，同时把这些位置对应标记在另一个数组temp中（即置这些位置上的值为1）；在遍历temp数组，找出置为1的位置，将对应matrix数组的行和列置为0即可。
  • 方法1代码实现
    class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] temp=new int[rows][cols];
        int flag=0;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(matrix[i][j]==0){
                    temp[i][j]=1;
                }
            }
        }
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(temp[i][j]==1){
                    for(int k=0;k<rows;k++){
                        matrix[k][j]=0;
                    }
                    for(int k=0;k<cols;k++){
                        matrix[i][k]=0;
                    }
                }
            }
        }
    }
}
  • 优化：可以将temp改成两个数组，分别记录每一行和每一列是否有零出现，可以减少内存空间的占用，使空间复杂度变为O（m+n）
    class Solution {
    public void setZeroes(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        boolean[] row = new boolean[rows];
        boolean[] col = new boolean[cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = col[j] = true;
                }
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

方法2

  • 分析：用矩阵的第一行和第一列代替方法一中的两个标记数组。因为我们不确定第一行和第一列本身有没有0，所有要先判断它们有没有0（即标记两个标记变量为true）。接着，循环判断用其他行与列，来标记第一行与第一列。然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。

  • 代码实现

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