LeetCode 刷题 [C++] 第73题.矩阵置零

题目描述

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

题目分析

1. 题目中要求使用原地算法：即直接在输入矩阵上进行修改。因此如果在输入矩阵上把行/列的值修改成0后，在接下来的遍历中就无法辨别矩阵中的0是原数值还是我们修改的0；
2. 因此我们需要使用两个标记数组来记录每一行和每一列是否有零出现；
3. 我们首先遍历该矩阵数组一次，如果某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为 true；
4. 然后我们再次遍历该数组，根据标记数组中的值来判断是否需要更新原数组中的值。

Code

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<bool> row(m),col(n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!matrix[i][j]) {
                    row[i] = col[j] = true;
                }
            }
        }
        for (int i = 0; i< m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (row[i] || col[j]) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22