Try   HackMD

Spiral Matrix

leetcode網址

Idea

分成四個case,keep四個方向: top, down, right, left,然後需要兩個位移動的index: i走x軸,j走y軸

  1. 往右走
    • 要bound住右邊
    • 走完後j=right(要往下走的column), i++(到下一層), right(右邊bound減一)
    • code
      ​​​​​​​​while(j<right){
      ​​​​​​​​    results.push_back(matrix[i][j]);
      ​​​​​​​​    j++;
      ​​​​​​​​}       
      ​​​​​​​​j=right-1;
      ​​​​​​​​right--;
      ​​​​​​​​i++;
      
  2. 往下走
    • 要bound住下界
    • 走完後i=down(要往左走的row), j(column往回走), down(下界bound減一)
    • code
      ​​​​​​​​while(i<down){
      ​​​​​​​​    results.push_back(matrix[i][j]);
      ​​​​​​​​    i++;
      ​​​​​​​​}
      ​​​​​​​​i=down-1;
      ​​​​​​​​down--;
      ​​​​​​​​j--;
      
  3. 往左走
    • 要bound住左邊
    • 走完後j=left(要往上走的column), i(到上一層), left++(左邊bound加一)
    • code
      ​​​​​​​​while(j>=left){
      ​​​​​​​​    results.push_back(matrix[i][j]);
      ​​​​​​​​    j--;
      ​​​​​​​​}
      ​​​​​​​​j=left;
      ​​​​​​​​left++;
      ​​​​​​​​i--;
      
  4. 往上走
    • 要bound住上邊
    • 走完後i=top(要往又走的row), j++(column往右走), top++(上邊bound加一)
    • code
      ​​​​​​​​while(i>top){                
      ​​​​​​​​    results.push_back(matrix[i][j]);
      ​​​​​​​​    i--;
      ​​​​​​​​}                                  
      ​​​​​​​​top++;
      ​​​​​​​​j++;
      ​​​​​​​​i=top;
      

Solution

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
Time Complexity: O (m × n)
✶⋆.˚ Space Complexity: O(1) additional space.

vector<int> spiralOrder(vector<vector<int>>& matrix) {

    int m=matrix.size(), n=matrix[0].size();
    int top=0, down=m, left=0, right=n;
    int dir=0, i=top, j=0;
    vector<int>results;
    while(results.size()<m*n){
        dir%=4;
        switch(dir){
            case 0:
                while(j<right){
                    results.push_back(matrix[i][j]);
                    j++;
                }       
                j=right-1;
                right--;
                i++;
                break;
            case 1:
                while(i<down){
                    results.push_back(matrix[i][j]);
                    i++;
                }
                i=down-1;
                down--;
                j--;
                break;
            case 2:
                while(j>=left){
                    results.push_back(matrix[i][j]);
                    j--;
                }
                j=left;
                left++;
                i--;
                break;
            default: 
                while(i>top){                
                    results.push_back(matrix[i][j]);
                    i--;
                }                                  
                top++;
                j++;
                i=top;
                break;
        }
        dir++;
    }
    return results;
}