leetcode 73: 矩阵置零

leetcode 73: 矩阵置零

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

示例 1:

leetcode 73: 矩阵置零

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

示例 2:

leetcode 73: 矩阵置零

输入: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]]

提示:

  • m == matrix.length

  • n == matrix[0].length

  • 1 <= m, n <= 200

  • -231 <= matrix[i][j] <= 231 - 1

进阶:

  • 一个直观的解决方案是使用 O(*m**n*) 的额外空间,但这并不是一个好的解决方案。

  • 一个简单的改进方案是使用 O(*m* + *n*) 的额外空间,但这仍然不是最好的解决方案。

  • 你能想出一个仅使用常量空间的解决方案吗?

Related Topics

数组

哈希表

矩阵

思路1:

  • 创建一个新的二维数组,遍历原来的二维数组,遇到0之后,修改新的二维数组中的行和列。

  • 修改完后,将新的二维数组赋值给原来的数组。

  • 空间复杂度为O(mn)

    public void setZeroes(int[][] matrix) {
    ​
        int row = matrix.length;//行
        int column = matrix[0].length;//列
        int[][] result = new int[row][column];
        for(int i = 0 ; i < row;i++){
            for(int j = 0 ; j <column;j++){
                result[i][j] = matrix[i][j];
            }
        }
        for(int i = 0 ; i < row;i++){
            for(int j = 0; j< column;j++){
                if(matrix[i][j] == 0){
                    //把行变为0
                    for(int k = 0; k < column;k++){
                        result[i][k] = 0;
                    }
                    //把列变为0
                    for(int k  = 0; k < row;k++){
                        result[k][j] = 0;
                    }
                }
            }
        }
        for(int i = 0 ; i < row;i++){
            for(int j = 0 ; j <column;j++){
                matrix[i][j] = result[i][j];
            }
        }
    }
        解答成功:
                执行耗时:1 ms,击败了90.80% 的Java用户
                内存消耗:42.5 MB,击败了7.90% 的Java用户
                

思路2:

使用2个标记数组,标记需要修改的行和列。

public void setZeroes(int[][] matrix) {
    int row = matrix.length;//行
    int column = matrix[0].length;//列
​
    boolean[] rowFlag = new boolean[row];
    boolean[] colFlag = new boolean[column];
    for(int i = 0 ; i <row;i++){
        for(int j = 0 ; j <column;j++){
            if(matrix[i][j] == 0){
                rowFlag[i] = true;
                colFlag[j] = true;
            }
        }
    }
    for(int i = 0 ; i <row;i++){
        for(int j = 0 ; j <column;j++){
            if(rowFlag[i] || colFlag[j]){
                matrix[i][j] = 0;
            }
        }
    }
}
    解答成功:
            执行耗时:0 ms,击败了100.00% 的Java用户
            内存消耗:42.9 MB,击败了5.54% 的Java用户

思路3:

空间复杂度为O(1)。参考leetcode官方

  • 将判断的需要行和列为0的标记存储再第一行和第一列。

  • 但是引发了一个新的问题,就是第一列和第一行是否需要修改,所以需要提前判断。

    public void setZeroes(int[][] matrix) {
        int row = matrix.length;//行
        int column = matrix[0].length;//列
        boolean rowFlag=false;
        boolean colFlag = false;
    ​
        for (int j= 0; j < column;j++){
            //判断第一行里面有没有0
            if(matrix[0][j]==0){
                rowFlag = true;
                break;
            }
        }
        for(int i = 0 ; i < row;i++){
            //判断第一列中有没有0
            if(matrix[i][0] == 0){
                colFlag = true;
                break;
            }
        }
        //如果某一行 某一列存在0 那么将第一行 第一列中的值修改为0
        for(int i = 0; i < row;i++){
            for(int j = 0; j < column;j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
    ​
        //修改
        for(int i = 1; i < row;i++){
            for(int j = 1; j < column;j++){
                if(matrix[i][0]==0 || matrix[0][j]==0){
                    matrix[i][j] = 0;
                }
            }
        }
    ​
        //判断行和列
        if(rowFlag){
            for(int j = 0 ; j < column;j++){
                matrix[0][j] = 0;
            }
        }
        if(colFlag){
            for(int i = 0; i < row;i++){
                matrix[i][0] = 0;
            }
        }

总结

思路2 性能最好,思路3空间复杂度最低。

上一篇:VsCode 赛博朋克风格


下一篇:大数据培训:Hive日常操作分享