Share my C++ solution,easy to understand


  • 0
    V

    Solution(1):O(mn) space

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            vector<int> ret;
            int row = matrix.size();
            if (row == 0)
                return ret;
            int col = matrix[0].size();
            if (col == 0)
                return ret;
                
            vector<vector<int>> isVisit(row, vector<int>(col, 0));
            int i = 0, j = 0;
            
            while (i >= 0 && i < row && j >= 0 && j < col && isVisit[i][j] == 0)
            {
                //toward right
                while (j < col && isVisit[i][j] == 0)
                {
                    isVisit[i][j] = 1;
                    ret.push_back(matrix[i][j++]);
                }
                j--;
                i++;
                
                //toward down
                while (i < row && isVisit[i][j] == 0)
                {
                    isVisit[i][j] = 1;
                    ret.push_back(matrix[i++][j]);
                }
                i--;
                j--;
                    
                //toward left
                while (j >= 0 && isVisit[i][j] == 0)
                {
                    isVisit[i][j] = 1;
                    ret.push_back(matrix[i][j--]);
                }
                j++;
                i--;
                
                //toward up
                while (i >= 0 && isVisit[i][j] == 0)
                {
                    isVisit[i][j] = 1;
                    ret.push_back(matrix[i--][j]);
                }
                i++;
                j++;
            }
            
            return ret;
        }
    };
    
    Solution (2):O(1) sapce
    
    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            vector<int> ret;
            int row = matrix.size();
            if (row == 0)
                return ret;
            int col = matrix[0].size();
            if (col == 0)
                return ret;
                
            int i = 0, j = 0, t = 0;
            int horzStep = col;
            int vertStep = row;
            
            while (horzStep && horzStep)
            {
                //toward right
                if (horzStep != col)
                {    
                    horzStep--;
                    i++;
                    j++;
                }
                if (horzStep < 1)
                    break;
                for (t = 1; t <= horzStep; t++, j++)
                    ret.push_back(matrix[i][j]);
                    
                //toward down
                vertStep--;
                if (vertStep < 1)
                    break;
                j--;
                i++;
                for (t = 1; t <= vertStep; t++, i++)
                    ret.push_back(matrix[i][j]);
                
                //toward left
                horzStep--;
                if (horzStep < 1)
                    break;
                i--;
                j--;
                for (t = 1; t <= horzStep; t++, j--)
                    ret.push_back(matrix[i][j]);
                    
                //toward up;
                vertStep--;
                if (vertStep < 1)
                    break;
                j++;
                i--;
                for (t = 1; t <= vertStep; t++, i--)
                    ret.push_back(matrix[i][j]);
            }
            
            return ret;
        }
    };

Log in to reply
 

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