0%

[Leetcode]73. Set Matrix Zeroes(C++)

题目描述

题目链接:73. Set Matrix Zeroes

Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

例子

例子 1

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

例子 2

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

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?

解题思路

题目要求很简单,遍历一个数组,遇到 0 的元素则将对应行和列的元素都设为 0。思路如下:

  • 首先肯定不能边做边改,因为这样会影响后续元素的判断(原本不是 0 的元素被设为 0)
  • 那么很直观可以想到一个 O(mn) 的方法,创建一个等大小的标志位数组,用来存储对应元素是否为 0,然后再根据标志位数据设置相对行和列的元素为 0 即可
  • 上述的方法有很大程度的数据是浪费的,因为对于一个行和列只需要由一个元素为 0 那么该行和该列都要设置为 0,所以我们只需要用 O(m + n) 的空间来存储哪些行和列有元素为 0 即可
  • 题目进一步要求有没有办法将所需空间降为常数级别的,我们可以想到用每一行和每一列的首元素作为标志位,注意这里必须是首元素,因为要保证标志位不受后续遍历的影响(假如用末元素作为标志位,那么我们先对标志位做出修改然后再判断,则可能会出现误判)。这种方法相当于将上一种方法用到的 O(m + n) 空间用数组中的第一行和第一列来代替了,但是这样的话可以想见第一行和和第一列的判断则会出现影响,这个问题很好解决,只需要用两个变量分别作为第一行和第一列的标志位即可(因此空间复杂度为矩阵的维度,这里是 2)

代码如下:

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
50
51
52
53
#include <vector>

class Solution {
public:
void setZeroes(std::vector<std::vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
bool first_row = false;
bool first_col = false;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
if (i == 0) {
first_row = true;
}
if (j == 0) {
first_col = true;
}
}
}
}

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

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

if (first_row) {
for (int i = 0; i < n; ++i) {
matrix[0][i] = 0;
}
}

if (first_col) {
for (int i = 0; i < m; ++i) {
matrix[i][0] = 0;
}
}
}
};
  • 时间复杂度: O(mn)
  • 空间复杂度: O(dim(matrix)) -> O(1)

GitHub 代码同步地址: 73.SetMatrixZeroes.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions