54.螺旋矩陣（Spiral Matrix）

• 題解
• • 規律，碰壁轉向
  • • 複雜度分析
    • Python
    • Java(待完成)
  • 逆時針旋轉（絕了）
  • • 先修
    • 算法流程
    • 複雜度分析
    • Python
    • Java(待完成)

題解

規律，碰壁轉向

碰到邊界，就轉向！

顯而易見，方向順序是固定的：右，下，左，上

我們利用通路數組 v i s i t e d visited visited和矩陣自身的範圍來構造邊界

1. 特判，當 m a t r i x matrix matrix為空時，傳回 [ ] [] []
2. 定義矩陣行數 M M M，矩陣列數 N N N。定義通路數組 v i s i t e d visited visited為 M ∗ N M*N M∗N數組，全部初始化為 F a l s e False False。定義方向清單 d i r e c t i o n s = [ [ 0 , 1 ] , [ 1 , 0 ] , [ 0 , − 1 ] , [ − 1 , 0 ] ] directions=[[0,1],[1,0],[0,-1],[-1,0]] directions=[[0,1],[1,0],[0,−1],[−1,0]]，分别對應右，下，左，上。定義目前通路行列索引 m = 0 m=0 m=0, n = 0 n=0 n=0。定義方向計數器 c o u n t = 0 count=0 count=0。定義結果清單 r e s res res
3. 因為矩陣含有 M ∗ N M*N M∗N個元素，是以周遊 M ∗ N M*N M∗N次，對于每次周遊：
   • 将 M a t r i x [ m ] [ n ] Matrix[m][n] Matrix[m][n]加入 r e s res res。并令通路數組 v i s i t e d [ m ] [ n ] visited[m][n] visited[m][n]置為 T r u e True True，代表這個位置已經通路了。
   • 取出目前方向 d i r _ x = d i r e c t i o n s [ c o u n t ] [ 0 ] , d i r _ y = d i r e c t i o n s [ c o u n t ] [ 1 ] dir\_x=directions[count][0],dir\_y=directions[count][1] dir_x=directions[count][0],dir_y=directions[count][1]，判斷下一步是否越界：
     • 越界條件由三部分組成： 0 < = m + d i r _ x < M 0<=m+dir\_x<M 0<=m+dir_x<M表示行在矩陣範圍内， 0 < = m + d i r _ y < N 0<=m+dir\_y<N 0<=m+dir_y<N表示列在矩陣範圍内， v i s i t e d [ m + d i r x ] [ n + d i r y ] visited[m+dir_x][n+dir_y] visited[m+dirx​][n+diry​]為 F a l s e False False表示下一步沒有被通路，即沒有碰到邊界。若同時滿足，說明下一步沒有越界，則更新 m , n m,n m,n， m + = d i r _ x ， n + = d i r _ y m+=dir\_x，n+=dir\_y m+=dir_x，n+=dir_y。
     • 若不滿足邊界條件，說明碰壁了，需要換方向，更新方向計數器 c o u n t = ( c o u n t + 1 ) % 4 count=(count+1)\%4 count=(count+1)%4，變換方向後是一定不會碰壁的 ，進而更新 m , n m,n m,n， m = m + d i r e c t i o n s [ c o u n t ] [ 0 ] m=m+directions[count][0] m=m+directions[count][0]， n = n + d i r e c t i o n s [ c o u n t ] [ 1 ] n=n+directions[count][1] n=n+directions[count][1]。
4. 傳回 r e s res res

複雜度分析

• 時間複雜度： O ( n ) O\left(n\right) O(n)，因為周遊一次矩陣。
• 空間複雜度： O ( n ) O\left(n\right) O(n)，需要額外的 v i s i t e d visited visited來儲存邊界。

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:return []
        res=[]
        M,N=len(matrix),len(matrix[0])
        visited=[[False]*N for _ in range(M)]
        directions=[[0,1],[1,0],[0,-1],[-1,0]]
        m,n,count=0,0,0
        for i in range(M*N):
            res.append(matrix[m][n])
            visited[m][n]=True
            dir_x,dir_y=directions[count][0],directions[count][1]
            if(0<=m+dir_x<M and 0<=n+dir_y<N and not visited[m+dir_x][n+dir_y]):
                m+=dir_x
                n+=dir_y
            else:
                count=(count+1)%4
                m,n=m+directions[count][0],n+directions[count][1]
        return res
         
           

Java(待完成)

逆時針旋轉（絕了）

先修

矩陣旋轉：

1. 順時針旋轉：先将矩陣轉置，再左右逆置。詳細可見48,旋轉圖像CSDN或48,旋轉圖像leetcode

   2.逆時針旋轉：先轉置，再上下逆置。道理和1一緻，可自己畫圖。

算法流程

是以，一個想法是：每次将矩陣的第一行取出來，放入 r e s res res，對剩下的矩陣逆時針旋轉，重複以上步驟。

将第一行加入 r e s res res，并從矩陣中删除。此時 r e s = [ 1 , 2 , 3 ] res=[1,2,3] res=[1,2,3]， M a t r i x Matrix Matrix如下：

轉置：

上下逆置：

重複以上步驟！

複雜度分析

暫未分析

Python

附上

map用法

zip用法

*參數的使用

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)
            matrix = list(map(list, zip(*matrix)))[::-1]
        return res
         
           

Java(待完成)