LeetCode矩阵置零_给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0

题目

给定一个 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的行列记下。再将对应的行列修改为0

2.对上面的空间的优化

创建List保存行、列的值来进行行列的修改，不使用数组，其余思路一致

3.不使用空间

遍历数组，遇到 0，就从 0 的位置行列展开变为 标记，遍历完后，在遍历数组，将标记的位置变为0

代码

1.暴力解法

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

//复制数组
        for(int i = 0; i < row;i++){
            for(int j = 0;j <col;j++){
                nums[i][j] = matrix[i][j];
            }
        }

        //保存数组中为0的行列 进行替换

        for(int i = 0; i <row;i++){
            for(int j = 0;j<col;j++){
                if(nums[i][j] == 0){
                    setZeroes(matrix,i,j);
                }
            }
        }
    }

    public static  void setZeroes(int[][] matrix,int hang,int lie){
        //将整行替换为 0
        for(int i = 0; i < matrix[0].length;i++){
            matrix[hang][i] = 0;
        }

        //将整列替换为 0
        for(int i = 0; i < matrix.length;i++){
            matrix[i][lie] = 0;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

2.空间优化

class Solution {
    public void setZeroes(int[][] matrix) {
        List<Integer> hang = new ArrayList<>();
        List<Integer> lie = new ArrayList<>();

        int row =  matrix.length;
        int col = matrix[0].length;

        //存储值为0 的行列
        for(int i = 0; i < row;i++){
            for(int j = 0; j < col;j++){
                if(matrix[i][j] == 0){
                    hang.add(i);
                    lie.add(j);
                }
            }
        }

        //将所在的行 变成0
        for(int hang1 :  hang){
            for(int i = 0; i < col;i++){
                matrix[hang1][i] = 0;
            }
        }

         //将所在的lie 变成0
        for(int lie1 :  lie){
            for(int i = 0; i < row;i++){
                matrix[i][lie1] = 0;
            }
        }
    }
}        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

3.不使用空间

public void setZeroes(int[][] matrix) {
        //不使用空间
        for(int i = 0; i < matrix.length;i++){
            for(int j = 0; j < matrix[0].length;j++){
                if(matrix[i][j] == 0){
                    //将所在行替换为 标记(遇到 0 和标记 直接跳过下一个)
                    for(int k =  0; k < matrix[0].length; k++){
                        if(matrix[i][k] != 0 && matrix[i][k] != '标'){
                            matrix[i][k] = '标';
                        }
                    }

                    //将所在列替换为 标记(遇到 0 和标记 直接跳过下一个)
                    for(int k =  0; k < matrix.length; k++){
                        if(matrix[k][j] != 0 && matrix[k][j] != '标'){
                            matrix[k][j] = '标';
                        }
                    }
                } 
            }
        }
//遍历数组，如果遇到标记就让他变为0
        for(int i =0;i  < matrix.length;i++){
            for(int j =0;j < matrix[0].length;j++){
                if(matrix[i][j] == '标'){
                    matrix[i][j] = 0;
                }
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/set-matrix-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。