By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、矩阵置零

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

示例 1:

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

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

示例 2:

输入: 
[
  [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.1、解题思路

两个hashset搞定

1.2、算法

  public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        /** 存储行和列的值 */
        Set<Integer> rows = new HashSet<>();
        Set<Integer> cols = new HashSet<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rows.add(i);
                    cols.add(j);
                }
            }
        }

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

1.3、测试

   @Test
    public void test(){
        int[][] matrix = {
                { 1,  0,  3,  4},
                { 5,  6,  7,  0},
                { 9, 0, 11, 12},
                {13, 14, 15, 16}
        };

        setZeroes(matrix);
        MatrixPrint.print(matrix);

    }

控制台：

 0,  0,  0,  0, 
 0,  0,  0,  0, 
 0,  0,  0,  0, 
13,  0, 15,  0,

​

ContactAuthor