Leetcode 73 矩阵置零_c语言给定一个 m*n 的矩阵,如果一个元素为0,则将其所在行和列的所有元素都设

题目

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

进阶：

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

解题思路

  普通思路不做赘述，这里仔细讲一下常量空间的解法。可以考虑利用矩阵边界（第 0 行和第 0 列）记录该列（行）中是否有 0 ，然后进行遍历，判断当前行（列）首元素是否为 0 ，如果为 0 ，则全置为 0 。恩，思路没问题，提交一下就 WA 了。如果边界上有 0 的话，在遍历更新后，边界会全变成 0 ，从而影响其他元素的更新，所以需要将边界和非边界（下标从[1, 1]开始）的元素分开考虑。可以一开始用标签记录边界上是否有 0 ，再利用边界对非边界元素进行更新，最后利用标签对边界进行更新。

代码

class Solution {
    public void setZeroes(int[][] matrix) {
        int lengthRaw = matrix.length, lengthCol = matrix[0].length;
        boolean hasZeroRaw = false, hasZeroCol = false;
        for (int i = 0; i < lengthCol; i++) {
            if (matrix[0][i] == 0) hasZeroRaw = true;
        }
        for (int i = 0; i < lengthRaw; i++) {
            if (matrix[i][0] == 0) hasZeroCol = true;
        }

        for (int i = 0; i < lengthRaw; i++) {
            for (int j = 0; j < lengthCol; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < lengthRaw; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < lengthCol; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int i = 1; i < lengthCol; i++) {
            if (matrix[0][i] == 0) {
                for (int j = 1; j < lengthRaw; j++) {
                    matrix[j][i] = 0;
                }
            }
        }

        if (hasZeroRaw) {
            for (int i = 0; i < lengthCol; i++) {
                matrix[0][i] = 0;
            }
        }
        if (hasZeroCol) {
            for (int i = 0; i < lengthRaw; i++) {
                matrix[i][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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46