Set Matrix Zeroes
ID
73
Data Type
Hashmap / Hashset
Difficulty
Medium
Tags
Completed Date
May 16, 2024
Preference
😰 Didn't Expect
Given an
m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.You must do it in place.
Example 1:
Example 2:
Constraints:
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
231 <= matrix[i][j] <= 231 - 1
Follow up:
- A straightforward 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?
题解
In-place
这个函数使用了一种空间复杂度为 O(1) 的方法，即在原矩阵上直接进行修改，而不需要额外的空间来存储行和列的信息。具体的实现步骤如下：
- 首先，函数定义了两个布尔变量
flag1和flag2，用于记录第一行和第一列是否需要被设为0。
- 然后，函数遍历矩阵的每个元素，如果发现某个元素为0，则将该元素所在的行的第一个元素和该元素所在的列的第一个元素都设为0，并且如果该元素在第一行或第一列，则将
flag1或flag2设为true。
- 接下来，函数再次遍历矩阵（这次从第二行和第二列开始），如果发现某个元素所在的行的第一个元素或该元素所在的列的第一个元素为0，则将该元素设为0。
- 最后，如果
flag1或flag2为true，则将第一行或第一列的所有元素设为0。
这个函数的时间复杂度为 O(mn)，其中 m 和 n 分别是矩阵的行数和列数，因为它需要遍历矩阵的所有元素两次。
如果我们直接将第一行或第一列中的0元素所在的行和列全部置为0，那么我们就会丢失原来第一行和第一列中的信息，因为它们被用作了标记位。为了解决这个问题，我们需要在开始处理其他行和列之前，先确定第一行和第一列是否应该被置为0。这就是为什么代码中需要使用
flag1 和 flag2，并且在处理其他行和列之后，再根据 flag1 和 flag2 的值来处理第一行和第一列。
暴力
先整体扫一遍找到0所在的位置，然后记录下需要置0的行列直接操作就行了