leetcode.矩阵.73矩阵置零-Java

1. 具体题目

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

示例 1:

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

2. 思路分析

先遍历原矩阵，找出所有值为 0 的元素，记录其行列的值，分别存入对应的 HashSet 中，之后遍历两个HashSet，将记录下来的行和列分别置零。

3. 代码

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

         HashSet<Integer> rows = new HashSet<>();

         HashSet<Integer> cols = new HashSet<>();

         for(int i = 0; i < matrix.length; i++){

             for(int j = 0; j < matrix[0].length; j++){

                 if(matrix[i][j] == 0){

                     rows.add(i);

                     cols.add(j);

                 }

             }

         }

         for(int row : rows){

             for(int col = 0; col < matrix[0].length; col++){

                 matrix[row][col] = 0;

             }

         }

         for(int col : cols){

             for(int row = 0; row < matrix.length; row++){

                 matrix[row][col] = 0;

             }

         }

     }

4. 思路优化

上述题解中，使用了额外的空间O(n + m)，对于空间进行优化，可以在遍历数组找 0 元素时，若找到则将其所在的行首和列首分别置0，之后再通过标志位进行置零操作。

巴特西

leetcode.矩阵.73矩阵置零-Java

最新文章

热门文章