Share my C++ solutions,easy to understand


  • 0
    V

    Solution(1):O(1) space

    class Solution {
    public:
        void setZeroes(vector<vector<int>>& matrix) {
            int m = matrix.size();
            if (m == 0)
                return;
            int n = matrix[0].size();
            if (n == 0)
                return;
            
            int i = 0, j = 0, k = 0;
            int firstRow = 1, firstCol = 1;
            
            for (i = 0; i < m; i++)
            {
                if (matrix[i][0] == 0)
                {
                    firstCol = 0;
                    break;
                }
            }
            for (j = 0; j < n; j++)
            {
                if (matrix[0][j] == 0)
                {
                    firstRow = 0;
                    break;
                }
            }
            
            for (i = 1; i < m ;i++)
            {
                for (j = 1; j < n; j++)
                {
                    if (matrix[i][j] == 0)
                    {
                        matrix[0][j] = 0;
                        matrix[i][0] = 0;
                    }
                }
            }
            
            for (i = 1; i < m; i++)
            {
                for (j = 1; j < n; j++)
                {
                    if (matrix[0][j] == 0 || matrix[i][0] == 0)
                            matrix[i][j] = 0;
                }
            }
            
            if (firstRow == 0)
            {
                for (i = 0; i < n; i++)
                    matrix[0][i] = 0;
            }
            
            if (firstCol == 0)
            {
                for (i = 0; i < m; i++)
                    matrix[i][0] = 0;
            }
        }
    };
    

    Solution(2):O(m+n) space

    class Solution {
    public:
        void setZeroes(vector<vector<int>>& matrix) {
            int m = matrix.size();
            if (m == 0)
                return;
            int n = matrix[0].size();
            if (n == 0)
                return;
            
            vector<int> mask(m+n, 1);
            int i = 0, j = 0, k = 0;
            
            for (i = 0; i < m; i++)
            {
                for (j = 0; j < n; j++)
                {
                    if (matrix[i][j] == 0)
                    {
                        mask[i] = 0;
                        mask[m+j] = 0;
                    }
                }
            }
            
            for (i = 0; i < m; i++)
            {
                if (mask[i] == 0)
                {
                    for (j = 0; j < n; j++)
                        matrix[i][j] = 0;
                }
            }
            
            for (j = 0; j < n; j++)
            {
                if (mask[m+j] == 0)
                {
                    for (i = 0; i < m; i++)
                        matrix[i][j] = 0;
                }
            }
        }
    };
    

    Solution(3):O(mn) space

    class Solution {
    public:
        void setZeroes(vector<vector<int>>& matrix) {
            int m = matrix.size();
            if (m == 0)
                return;
            int n = matrix[0].size();
            if (n == 0)
                return;
            
            vector<vector<int>> mask(m,vector<int>(n, 1));
            int i = 0, j = 0, k = 0;
            for (i = 0; i < m; i++)
            {
                for (j = 0; j < n; j++)
                {
                    if (matrix[i][j] == 0)
                        mask[i][j] = 0;
                }
            }
            
            for (i = 0; i < m; i++)
            {
                for (j = 0; j < n; j++)
                {
                    if (mask[i][j] == 0)
                    {
                        for (k = 0; k < m; k++)
                            matrix[k][j] = 0;
                            
                        for (k = 0; k < n; k++)
                            matrix[i][k] = 0;
                    }
                }
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.