#54. Spiral Matrix

題目描述

給你一個m x n的矩陣martix，以螺旋順序回傳所有的矩陣元素。

限制條件

1. m == matrix.length
2. n == matrix[i].length
3. 1 <= m, n <= 10
4. -100 <= matrix[i][j] <= 100

解題思路

這一題題目描述了螺旋順序，用實例來解釋會比較好理解。

例：

1 - 2 - 3
		|
8 - 9   4
|		|
7 - 6 -	5

從例子中我們可以看到所謂的螺旋順序其實就是以順時鐘順序逐漸向內直到走完所有元素的順序。

Array Solution

按照題目的要求，我們會知道解題步驟為：

1. 從[0,0]向右讀取元素，直到碰到右邊邊界或者已經處理過的元素。
2. 當碰到邊界或已經處理過的元素後，依照現在的方向調整讀取方向，方向的轉換為「右->下」、「下->左」、「左->上」、「上->右」。
3. 重複步驟直到處理完所有的元素。

邊界與處理過的元素，可以把他想像成是一道牆，當撞到牆後就轉向，所以我們可以根據這個特性去設立四個方向的邊界牆，topBound、bottomBound、leftBound、rightBound。

再來我們會需要當前的位置，(x,y)，與前進的方向direction。

最後，只要確認四周都是邊界則代表處理完所有的元素，可以回傳答案。

public class Solution {    
    public IList<int> SpiralOrder(int[][] matrix) {        
        var ans = new List<int>();        
        int topBound = 0;
        int bottomBound = matrix.Length-1;
        int leftBound = 0;
        int rightBound = matrix[0].Length-1;
        int x = 0;
        int y = 0;
        int direction = 1; // right, down, left, up = 1, 2, 3, 4
        int cells = matrix.Length * matrix[0].Length;
        for(int i=0;i<cells;i++){            
            ans.Add(matrix[x][y]);
			//the last element condition.
            if(x-1==topBound && x+1==bottomBound && y-1==leftBound && y+1==rightBound) return ans;
            if(direction == 1){
                if(y < rightBound) y++;
                else{
					// trim bound
                    topBound++;
					// next cell's position
                    x++;
					//right -> down
                    direction = 2;                    
                }                
            }else if(direction == 2){
                if(x < bottomBound) x++;
                else{
					// trim bound
                    rightBound--;
					// next cell's position
                    y--;
					//down -> left
                    direction = 3;
                }
            }else if(direction == 3){
                if(y > leftBound) y--;
                else{
					// trim bound
                    bottomBound--;
					// next cell's position
                    x--;
					//left -> up
                    direction = 4;
                }
            }else if(direction == 4){                
                if(x > topBound) x--;
                else{
					// trim bound
                    leftBound++;
					// next cell's position
                    y++;
					//up -> right
                    direction = 1;
                }
            }
        }        
        return ans;
    }    
}

複雜度分析：

• 時間複雜度：要檢查完所有的格子，因此時間複雜度為O(m*n)。
• 空間複雜度：不計算答案所佔用的空間，則空間複雜度為O(1)。

學習重點

• Array