[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）

代码如下：

#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