73. 矩阵置零

题目

image-20240913160209125 image-20240913160326372

解法

常规的解法常见，在不考虑空间复杂度的情况下，可以重新开一个同等大小的矩阵保存数据集，之后替换即可，也可以在遍历的过程中使用两个数组预先保存本来就是0 的位置，在本地置零操作完成后再去处理数组中的内容，空间复杂度得到一定优化。

如果矩阵中的元素没有包括一个int所能表示的所有范围的话，还是可以用标志变量去标记原本的0和新变的0。时间和空间复杂度分别是Om*n，O1

代码

这个方法是将全局的0都映射到数组上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> row(m), col(n);
    
       //全局的0映射
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!matrix[i][j]) {
                    row[i] = col[j] = true;
                }
            }
        }
    
    //根据映射的0改变值
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

如果想要实现题目中给出的原地算法，考虑最优空间复杂度的情况下，就需要使用以下代码，主要步骤是先记录第一行和第一列是否存在0，使用两个int存储true和false进行控制，然后将整个矩阵中非第一行和第一列的位置上所有为0的映射到第一行和第一列上，本来这些位置都是要置零的，所以没有错误。

之后再去遍历非第一行和第一列的数据，行和列对应的第一行和第一列数据但凡是有0 的，该位置上的值统统变为0。

最后再根据之前设计的两个int记录的第一行和第一列是否有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
47
48
49
void setZeroes(vector<vector<int>>& matrix) {
	int m = matrix.size();
	int n = matrix[0].size();
	int flag_col0 = false, flag_row0 = false;
    
    //记录第一列是否存在0
	for (int i = 0; i < m; i++) {
		if (!matrix[i][0]) {
			flag_col0 = true;
		}
	}
    
    //记录第一行是否存在0
	for (int j = 0; j < n; j++) {
		if (!matrix[0][j]) {
			flag_row0 = true;
		}
	}
    
    //将矩阵中除第一行和第一列的0映射到第一行和第一例
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			if (!matrix[i][j]) {
				matrix[i][0] = matrix[0][j] = 0;
			}
		}
	}
    
    //根据映射的0改变对应的值
	for (int i = 1; i < m; i++) {
		for (int j = 1; j < n; j++) {
			if (!matrix[i][0] || !matrix[0][j]) {
				matrix[i][j] = 0;
			}
		}
	}
    
    //对第一行和第一列最后进行操作
	if (flag_col0) {
		for (int i = 0; i < m; i++) {
			matrix[i][0] = 0;
		}
	}
	if (flag_row0) {
		for (int j = 0; j < n; j++) {
			matrix[0][j] = 0;
		}
	}
}