鏈接：https://leetcode-cn.com/problems/spiral-matrix

題目：

給你一個(gè) m 行 n 列的矩陣 matrix ，請(qǐng)按照 順時(shí)針螺旋順序 ，返回矩陣中的所有元素。

示例 1：

示例1.png

輸入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
輸出：[1,2,3,6,9,8,7,4,5]

示例 2：

示例2.png

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

提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

解題思路

方法一：模擬

可以模擬螺旋矩陣的路徑。初始位置是矩陣的左上角，初始方向是向右，當(dāng)路徑超出界限或者進(jìn)入之前訪問過的位置時(shí)，順時(shí)針旋轉(zhuǎn)，進(jìn)入下一個(gè)方向。

判斷路徑是否進(jìn)入之前訪問過的位置需要使用一個(gè)與輸入矩陣大小相同的輔助矩陣 \textit{visited}visited，其中的每個(gè)元素表示該位置是否被訪問過。當(dāng)一個(gè)元素被訪問時(shí)，將 \textit{visited}visited 中的對(duì)應(yīng)位置的元素設(shè)為已訪問。

如何判斷路徑是否結(jié)束？由于矩陣中的每個(gè)元素都被訪問一次，因此路徑的長度即為矩陣中的元素?cái)?shù)量，當(dāng)路徑的長度達(dá)到矩陣中的元素?cái)?shù)量時(shí)即為完整路徑，將該路徑返回。

方法一的Golang代碼實(shí)現(xiàn)

//方法一 模擬
func spiralOrder(matrix [][]int) []int {
    rows, columns := len(matrix), len(matrix[0])
    totals := rows * columns
    visited := make([][]bool, rows)
    for i := 0 ;i< rows;i++ {
        visited[i] = make([]bool, columns)
    }
    directions := [][]int{{0,1}, {1,0}, {0,-1}, {-1, 0}} //這是從左上角開始，順時(shí)針旋轉(zhuǎn)時(shí)，下標(biāo)的增量值，所以順序不能倒
    var (
        row, column = 0, 0
        directionindex = 0
        order = make([]int, totals)
    )
    for i := 0;i< totals;i++{
        order[i] = matrix[row][column]
        visited[row][column] = true
        nextrow, nextcolumn := row + directions[directionindex][0], column + directions[directionindex][1]
        //注意此處幾項(xiàng)的順序，visited[nextrow][nextcolumn]必須放在最后，因?yàn)橐扰袛嗤阯extrow,nextcolumn是否合適，才能再判斷visited[nextrow][nextcolumn]否則可能越界或者不存在。
        if nextrow < 0 ||nextrow >= rows || nextcolumn < 0 || nextcolumn >= columns ||  visited[nextrow][nextcolumn]  {
            directionindex = (directionindex + 1 ) % 4
        }
       row += directions[directionindex][0]
       column += directions[directionindex][1]
    }
    return order
}

方法一的復(fù)雜度分析

時(shí)間復(fù)雜度：O(mn)O(mn)，其中 mm 和 nn 分別是輸入矩陣的行數(shù)和列數(shù)。矩陣中的每個(gè)元素都要被訪問一次。

空間復(fù)雜度：O(mn)O(mn)。需要?jiǎng)?chuàng)建一個(gè)大小為 m \times nm×n 的矩陣 \textit{visited}visited 記錄每個(gè)位置是否被訪問過。

方法二：按層模擬

可以將矩陣看成若干層，首先輸出最外層的元素，其次輸出次外層的元素，直到輸出最內(nèi)層的元素。

定義矩陣的第 kk 層是到最近邊界距離為 kk 的所有頂點(diǎn)。例如，下圖矩陣最外層元素都是第 11 層，次外層元素都是第 22 層，剩下的元素都是第 33 層。

[[1, 1, 1, 1, 1, 1, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 2, 3, 3, 3, 2, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 1, 1, 1, 1, 1, 1]]
對(duì)于每層，從左上方開始以順時(shí)針的順序遍歷所有元素。假設(shè)當(dāng)前層的左上角位于 (top,left)，右下角位于 (bottom,right)，按照如下順序遍歷當(dāng)前層的元素。

從左到右遍歷上側(cè)元素，依次為 (top,left) 到 (top,right)。

從上到下遍歷右側(cè)元素，依次為 (top+1,right) 到 (bottom,right)。
如果 left<right 且 top<bottom，則從右到左遍歷下側(cè)元素，依次為 (bottom,right?1) 到 (bottom,left+1)，以及從下到上遍歷左側(cè)元素，依次為 (bottom,left) 到 (top+1,left)。

遍歷完當(dāng)前層的元素之后，將 left 和 top 分別增加 11，將 right 和 bottom 分別減少 11，進(jìn)入下一層繼續(xù)遍歷，直到遍歷完所有元素為止。

image.png

方法二的Golang代碼實(shí)現(xiàn)

func spiralOrder(matrix [][]int) []int {
   rows, columns := len(matrix), len(matrix[0])
   totals := rows * columns
   var (
       left, right = 0, columns-1
       top, bottom = 0, rows-1
       order = make([]int, totals)
       index = 0
   )
   for left <= right && top <= bottom {
       //從左上到右上
       for column := left ;column <= right;column++{
           order[index] = matrix[top][column]
           index ++
       }
       //從右上到右下
       for row := top + 1; row <= bottom;row++ {
           order[index] = matrix[row][right]
           index++
       }
       if left < right && top < bottom {
           //從右下到左下
           for column := right - 1; column > left;column--{
               order[index] = matrix[bottom][column]
               index++
           }
           //從左下到左上
           for row := bottom; row > top; row--{
               order[index] = matrix[row][left]
               index++
           }
       }
       left++
       right--
       top++
       bottom--
   }
   return order
}

方法二的復(fù)雜度分析

復(fù)雜度分析

時(shí)間復(fù)雜度：O(mn)O(mn)，其中 mm 和 nn 分別是輸入矩陣的行數(shù)和列數(shù)。矩陣中的每個(gè)元素都要被訪問一次。

空間復(fù)雜度：O(1)O(1)。除了輸出數(shù)組以外，空間復(fù)雜度是常數(shù)。