讨论/《中级算法》 - 矩阵置零/
《中级算法》 - 矩阵置零
共 13 个回复

原地算法,使用常数额外空间
先判断第一行第一列是否为0,然后把其他为0的行列放到对应第一行列的位置,再置0,最后处理第一行第一列的置0

class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        boolean isRowZero = false, isCowZero = false;
        for (int[] ints : matrix) {
            if (ints[0] == 0) {
                isCowZero = true;
                break;
            }
        }
        for (int i = 0; i < matrix[0].length; i++) {
            if (matrix[0][i] == 0) {
                isRowZero = true;
                break;
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] =0;
                }
            }
        }
        for (int i = 1; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < matrix[0].length; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int i = 1; i < matrix[0].length; i++) {
            if(matrix[0][i] == 0){
                for (int j = 1; j < matrix.length; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
        if(isCowZero) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
        if(isRowZero) {
            for (int i = 0; i < matrix[0].length; i++) {
                matrix[0][i] = 0;
            }
        }

    }
}
3

使用m+n的额外空间

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean[] zeros = new boolean[m+n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] == 0){
                    // 将行信息为0的存放在数组【0-m】下标
                    zeros[i] = true;
                    // 将列信息为0的存放在数组【m-m+n】下标
                    zeros[m+j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 该行有0,将该元素置0
                if(zeros[i]){
                    matrix[i][j] = 0;
                }
                // 改列有0.该元素置0
                if(zeros[j+m]){
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
3

暴力法
基本想法:
记录需要置为0的行序和列序,再遍历置0即可!

class Solution {
    public void setZeroes(int[][] matrix) {
        //行序集
        Set<Integer> xSet = new HashSet<>();
        //列序集
        Set<Integer> ySet = new HashSet<>();
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    if (!xSet.contains(i)) {
                        xSet.add(i);
                    }
                    if (!ySet.contains(j)) {
                        ySet.add(j);
                    }
                }
            }
        }
        for (Integer x : xSet) {
            for (int j = 0; j < n; j++) {
                matrix[x][j] = 0;
            }
        }
        for (Integer y : ySet) {
            for (int i = 0; i < m; i++) {
                matrix[i][y] = 0;
            }
        }
    }
}

复杂度分析:
时间复杂度: O(mn) 空间复杂度: O(m+n)
运行截图:
image.png
进阶解法:(参考大佬们的解法!)
基本思路:
矩阵[1-m][1-n]置零,先遍历第一行标记是否需要将第一行置0,同理遍历第一列标记是否需要将第一列置0,再遍历矩阵[2-m][2-n]部分,如果需要置0本列和本行则修改matrix[i][0]和matrix[0][j]为0作为标记行或列是否需要置0,最后再遍历[2-m][2-n]部分并置0以及处理第一行和第一列即可!

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

        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;
                }
            }
        }
        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(firstRow){
            for (int j = 0; j < n; j++) {
               matrix[0][j]=0;
            }
        }
        if (firstCol) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

时间复杂度分析:
时间复杂度:O(nm) 空间复杂度: O(1)
image.png

2

image.png

空间复杂度O(1)

class Solution {
    public void setZeroes(int[][] matrix) {
         //数组行列数
        int raw = matrix.length;
        int col = matrix[0].length;
        //检查第一列是否有0
        boolean rowHasZero = false;
        boolean colHasZero = false;
        for (int i=0;i<raw;i++){
            if (matrix[i][0]==0){
                colHasZero=true;
                break;
            }
        }
        //检查第一行是否有0
        for (int i=0;i<col;i++){
            if (matrix[0][i]==0){
                rowHasZero=true;
                break;
            }
        }
        //使用第一行第一列标记其余行列是否有0
        for(int i=1;i<matrix.length;i++){
            for(int j=1;j<matrix[i].length;j++){
                if(matrix[i][j]==0){
                   matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
        //利用第一行第一列的标0 强开,将martix中的数字标0
        for(int i=1;i<matrix.length;i++){
            for(int j=1;j<matrix[i].length;j++){
                if(matrix[i][0]==0||matrix[0][j]==0){
                    matrix[i][j]=0;
                }
            }
        }
        //第一行第一列标0
        if(rowHasZero){
            for (int i=0;i<col;i++){
                matrix[0][i]=0;
            }
        }
        if(colHasZero){
            for (int i=0;i<raw;i++){
                matrix[i][0]=0;
            }
        }
        System.out.println(Arrays.deepToString(matrix));
    }
}
1

还行,已经修了

判例
[[1,2,3,4],[5,0,7,8],[0,10,11,12],[13,14,15,0]]
为啥答案是
[[0,0,3,0],[0,0,7,0],[0,0,11,0],[0,0,15,0]]
而不是
[[0,0,3,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
7,11,15都在有0的一行里啊?

暴力解决,哈哈哈哈哈

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        HashSet<Integer> mZero = new HashSet<Integer>();
        HashSet<Integer> nZero = new HashSet<Integer>();
        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n; j ++){
                //System.out.println(matrix[i][j]);
                if(matrix[i][j] == 0){
                   mZero.add(i);
                   nZero.add(j); 
                }
            }
        }

        for(int i = 0; i < m; i ++){
            for(int j = 0; j < n ; j ++){
                if(mZero.contains(i) || nZero.contains(j)){
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

简单说就是把中间的0投影到左边和上边

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int width=matrix.size();
        int length=matrix[0].size();
        bool lenIsZero=false,widIsZero=false;
        for(int i=0;i<length;i++)
        {
            if(matrix[0][i]==0)
            {
                lenIsZero=true;
                break;
            }
        }
        for(int i=0;i<width;i++)
        {
            if(matrix[i][0]==0)
            {
                widIsZero=true;
                break;
            }
        }
        //0投影到左边和上边
         for (int i = 1; i < width; i++) {
            for (int j = 1; j < length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        //根据投影重制
        for (int i = 1; i < width; i++) {
            for (int j = 1; j < length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        //最后根绝bool值决定是否要重制第一列和第一行
        if(widIsZero) {
            for (int i = 0; i < width; i++) {
                matrix[i][0] = 0;
            }
        }
        if(lenIsZero) {
            for (int i = 0; i < length; i++) {
                matrix[0][i] = 0;
            }
        }
    }
};
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        vector<int> cols;
        for (int i = 0; i < matrix.size(); i++) {
            bool flag = false;
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] == 0) {
                    cols.push_back(j);
                    flag = true;
                }
            }
            if (flag)
                matrix[i].assign(matrix[i].size(), 0);
        }
        for (int i = 0; i < matrix.size(); i++) {
            for (auto j : cols) {
                matrix[i][j] = 0;
            }
        }
        
    }
};

谢谢,嗯嗯,有的,ArrayList可以替代