[数据结构与算法]leetcode题解：矩阵置零

题目描述

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

进阶：

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

来源：力扣（LeetCode）

题目分析

题目其实很简单，主要就是题目中要求的如何来缩减额外空间（注意：是空间复杂度，刚开始看成了时间复杂度，纠结好久）。

思路1：最基础的，设置一个flag矩阵来标志原数组位置是原本为0还是被变换为0；然后进行遍历，检测到原本是0的元素则将其行列置零?
空间复杂度 o(mn)； 执行用时：16 ms ? 内存消耗：13.2 MB?

    void setLenRowToZero(vector<vector<int>> &matrix, vector<vector<int>> &flag, int x, int y){
        int m = matrix.size();
        int n = matrix[0].size();

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

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

    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        // 额外空间(mn)
        vector<vector<int>> flag(m, vector<int>(n, 0));

        for(int x = 0; x < m; x++){
            for(int y = 0; y < n; y++){
                if (!matrix[x][y] && !flag[x][y]){
                    setLenRowToZero(matrix, flag, x, y);
                }
            }
        }
    }

思路2： 上个思路中因建立了一个同等大小的标示矩阵，占用内存过大。因此采用两个set，只保存需要置零的行列index
空间复杂度 o(m+n)；??执行用时：8 ms ? 内存消耗：12.9 MB(两个1维的set,居然相比于2维的vector没有降低多少内存，，，)

    void setZeroes(vector<vector<int>> &matrix){
        int m = matrix.size();
        int n = matrix[0].size();

        // 额外空间(m+n)
        set<int> rows;
        set<int> lens;

        for (int x = 0; x < m; x++){
            for (int y = 0; y < n; y++){
                if (!matrix[x][y]){
                    rows.insert(x);
                    lens.insert(y);
                }
            }
        }

        while(!rows.empty()){
            int x = *rows.begin();
            for (int j = 0; j < n; j++)
                matrix[x][j] = 0;
            rows.erase(rows.begin());
        }

        while(!lens.empty()){
            int y = *lens.begin();
            for (int j = 0; j < m; j++)
                matrix[j][y] = 0;
            lens.erase(lens.begin());
        }
    }

思路3：进阶，使用matrix自身的第一行第一列来标示该行/列是否需要置零；只需要对第一行第一列单独建立标示即可
空间复杂度 o(1) （两个标识）执行用时：16 ms ? 内存消耗：12.9 MB(emmmmm..........看来matrix本身就占用了这么大内存，压不下去了)

    void setZeroes(vector<vector<int>> &matrix){
        int m = matrix.size();
        int n = matrix[0].size();

        // 额外空间(1)
        bool row1_0 = false, col1_0 = false;
        for(int i = 0; i< n; i++){
            if (!matrix[0][i]){
                row1_0 = true;
                break;
            }
        }
        for(int i = 0; i< m; i++){
            if (!matrix[i][0]){
                col1_0 = true;
                break;
            }
        }

        for(int x = 1; x < m; x++){
            for(int y = 1; y < n; y++){
                if (!matrix[x][y]){
                    matrix[0][y] = matrix[x][0] = 0;
                }
            }
        }

        for(int x = 1; x < m; x++){
            for(int y = 1; y<n; y++){
                if (!matrix[0][y] || !matrix[x][0])
                    matrix[x][y] = 0;
            }
        }

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