Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:
Input: [ [1,1,1], [1,0,1], [1,1,1] ] Output: [ [1,0,1], [0,0,0], [1,0,1] ]Follow up:
A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution?
方法一： 使用两个set分别来存储需要设置为0的行和列
class Solution { public void setZeroes(int[][] matrix) { Set<Integer> row = new HashSet<>(); Set<Integer> col = new HashSet<>(); int n = matrix.length; int m = matrix[0].length; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (matrix[i][j] == 0) { row.add(i); col.add(j); } } } for (int r : row) { for (int j = 0; j < m; j++) { matrix[r][j] = 0; } } for (int c : col) { for (int i = 0; i < n; i++) { matrix[i][c] = 0; } } } }方法二： 不使用额外空间。 利用数组本身的空间来存储信息。 需要先把第一行和第一列遍历一遍，看一下第一行和第一列是否存在0，然后记录一下。之后，就可以把第一行和第一列当做是存储空间，来存状态即可。
class Solution { public void setZeroes(int[][] matrix) { int n = matrix.length; int m = matrix[0].length; // 记录第一行和第一列的答案 boolean firstRowIsZero = false; boolean firstColIsZero = false; for (int i = 0; i < m; i++) { if (matrix[0][i] == 0) { firstRowIsZero = true; break; } } for (int i = 0; i < n; i++) { if (matrix[i][0] == 0) { firstColIsZero = true; break; } } // 在第一行和第一列上做标记 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } // 利用第一行和第一列，将剩余的格子标0 for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } // 最后，看第一行和第一列的答案 if (firstRowIsZero) { for (int i = 0; i < m; i++) { matrix[0][i] = 0; } } if (firstColIsZero) { for (int i = 0; i < n; i++) { matrix[i][0] = 0; } } } }