题目

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

示例 1：

img

1
2
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

img

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]]

提示：

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1

进阶：

  • 一个直观的解决方案是使用 O(*m**n*) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(*m* + *n*) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗？

题解

这题的思路还是比较简单的，也就是直观的方法，需要用到一个标记数组，遍历matrix，遇到0的时候就进行标记（标记时跳过已经为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
class Solution {
    public void setZeroes(int[][] matrix) {
        // 需要遍历数组，遇到0置0，然后标记不需要再访问
        int m = matrix.length, n = matrix[0].length;
        // 默认为false说明全是0
        boolean[][] flag = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0 && flag[i][j] == false) {
                    // 先处理列，再处理行
                    for (int k = 0; k < n; k++) {
                        if (matrix[i][k] != 0) {
                            matrix[i][k] = 0;
                            flag[i][k] = true;
                        }
                    }
                    for (int k = 0; k < m; k++) {
                        if (matrix[k][j] != 0) {
                            matrix[k][j] = 0;
                            flag[k][j] = true;
                        }
                    }
                }
            }
        }
    }
}