算法（1）——螺旋矩陣

前言

關于螺旋矩陣，這道算法題，當初出去面試碰到了兩次，怪自己當初面完試沒有及時回來總結整理。導緻兩次遇到了這個原題，兩次都沒答上來。最近自己開始在LeetCode上刷算法題，又刷到了這道題，經過整理總結後，拿到這裡和大家分享一下。

廢話不多說，上題：

題目

給定一個包含 m x n 個元素的矩陣（m 行, n 列），請按照順時針螺旋順序，傳回矩陣中的所有元素。

示例 1:

輸入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
輸出: [1,2,3,6,9,8,7,4,5]
           

示例 2:

輸入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
輸出: [1,2,3,4,8,12,11,10,9,5,6,7]
           

分析

可以仔細觀察示例1或示例2，這裡為了友善，咱們再多寫一組示例：

示例3：

輸入:
[
  [1,  2,  3,  4],
  [5,  6,  7,  8],
  [9, 10, 11, 12],
  [13,14, 15, 16]
]
輸出: [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
           

仔細觀察可以發現，螺旋矩陣正如其名，它是按照螺旋輸出矩陣中的數字。而且是有規律的,分四步:

第一步：先輸出最頂部的一行（從左到右），依次是[1,2,3,4]；

第二步：再輸出最右邊的一列（從上到下，除去最頂部已經輸出的4）,依次是[8，12，16];

第三步：再輸出最底部一行（從右到左，除去最右邊已經輸出的16），依次是[15,14,13];

第四步：再輸出最左邊一列（從下到上，除去最底部已經輸出的13和最頂部已經輸出的1），依次是[9,5];

好了，這樣經過四步就已經完成了螺旋矩陣的第一圈螺旋的輸出，接下來，還有未輸出的[6,7,11,10],又可以看作螺旋矩陣的第二圈螺旋的輸出，繼續重複上述四步就可以把[6,7,11,10]輸出。

由分析得出結論：經過分析可知，其實螺旋矩陣的輸出，分别先後對應上、右、下、左的輸出，而且是一圈繞一圈，循環輸出。

實作預想：可以把螺旋矩陣，看成一個二維數組結構，其實就是通過循環列印二維數組結構中元素的輸出。隻不過這個輸出是按照上、右、下、左的順序輸出，循環進行。

具體實作

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> resultList=new ArrayList();
        if(matrix==null||matrix.length==0){//判空
            return resultList;
        }

        /**
          *分别定義左、右、上、下的四個範圍的初始索引
        */
        int left=0;
        int right=matrix[0].length-1;
        int top=0;
        int bottom=matrix.length-1;
        

        while(true){//進行循環

            //列印頂部資料
            for(int i=left;i<=right;i++){
               resultList.add(matrix[top][i]);
            }
            if(++top>bottom){//進行判斷，如果頂部索引+1大于底部索引時，就跳出循環
                break;
            }

            //列印右邊資料
            for(int i=top;i<=bottom;i++){
                resultList.add(matrix[i][right]);
            }
            if(--right<left){//進行判斷，如果右邊索引-1小于左邊索引時，就跳出循環
                break;
            }

            //列印底部資料
            for(int i=right;i>=left;i--){
                resultList.add(matrix[bottom][i]);
            }
            if(--bottom<top){//進行判斷，如果底部索引-1小于頂部索引時，就跳出循環
                break;
            }

            //列印左邊資料
            for(int i=bottom;i>=top;i--){
                resultList.add(matrix[i][left]);
            }
            if(++left>right){//進行判斷，如果左邊索引+1大于右邊索引時，就跳出循環
                break;
            }
        }
        return resultList;
        
    }
}
           

總結

好了，到這裡關于螺旋矩陣的這道題的解答就和大家分享完畢了，其實就是一個螺旋循環去輸出一個二維數組。關鍵在于了解算法中的螺旋順序輸出，以及跳出循環的條件。菜鳥一個，大家有什麼問題可以留言，多多指教。