interviewalgo
, , ,
Source
Edit
History

73. 矩阵置零

Introduction

Question: 73. 矩阵置零

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

进阶：

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

 

示例 1：

输入：matrix = 1,1,1],[1,0,1],[1,1,1
输出：1,0,1],[0,0,0],[1,0,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

解法一

Analysis

由于要原地进行操作，所以肯定需要一个方式来利用原数组作为额外空间。这里需要的额外空间的大小为O(m+n)。我们可以先找到第一个为零的位置(i,j)。由于第i行和第j列是一定会被置零的，所以我们可以利用他们来存储对应行列是否要置零的flag，然后在置零即可。

Implement

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
pair<int,int> findZeros(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    for(int i = 0;i < m; i++) {
        for(int j = 0;j < n; j++) {
            if (matrix[i][j] == 0) {
                return make_pair(i, j);    
            }
        }
    }
    return make_pair(-1,-1);
}
void setZeroes(vector<vector<int>>& matrix) {
    auto p = findZeros(matrix);

    int iz = p.first, jz = p.second;
    if (iz == -1) return ;
    int m = matrix.size();
    int n = matrix[0].size();
    for(int i = iz+1;i < m;i++) {
        for(int j = 0; j < n;j++) {
            if (matrix[i][j] == 0) {
                matrix[i][jz] = 0;
                matrix[iz][j] = 0;
            }
        }
    }


    for(int i = 0;i < m;i++) {
        if (i == iz) continue;
        for (int j = 0;j < n;j++) {
            if (j == jz) continue;
            if (matrix[i][jz] == 0 || matrix[iz][j] == 0)
                matrix[i][j] = 0;
        }
    }
    for(int i = 0;i < m; i++) {
        matrix[i][jz] = 0;
    }
    for(int j = 0;j < n; j++) {
        matrix[iz][j] = 0;
    }

}