Title

輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數字。

示例 1：

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

示例 2：

輸入：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]

限制：

0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

Solve

宏觀調度：

這題貌似在哪本書上見過，還是道經典例題。

可以將矩陣看成若干層，首先打印最外層的元素，其次打印次外層的元素，直到打印最內層的元素。

定義矩陣的第 k 層是到最近邊界距離為 k 的所有頂點。例如，下圖矩陣最外層元素都是第 1 層，次外層元素都是第 2 層，剩下的元素都是第 3 層。

[[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]]

對于每層，從左上方開始以順時針的順序遍歷所有元素。假設當前層的左上角位于(top,left)，右下角位于(bottom,right)，按照如下順序遍歷當前層的元素。

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

從上到下遍歷右側元素，依次為 (top+1,right) 到 (bottom,right)。

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

遍歷完當前層的元素之后，將left 和 top 分別增加 1，將 right 和 bottom 分別減少 1，進入下一層繼續遍歷，直到遍歷完所有元素為止。

復雜度分析

時間復雜度：O(mn)，其中 m 和 n 分別是輸入矩陣的行數和列數。矩陣中的每個元素都要被訪問一次。

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

Code

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:if not matrix or not matrix[0]:return []res, up, left, down, right = [], 0, 0, len(matrix), len(matrix[0])while up < down + 1 and left < right + 1:for i in range(left, right):res.append(matrix[up][i])up += 1if up > down - 1:breakfor i in range(up, down):res.append(matrix[i][right - 1])right -= 1if left > right - 1:breakfor i in range(right - 1, left - 1, -1):res.append(matrix[down - 1][i])down -= 1if up > down - 1:breakfor i in range(down - 1, up - 1, -1):res.append(matrix[i][left])left += 1if left > right - 1:breakreturn res

---

zip

在題解中看到一種騷操作。

將矩陣第一行的元素添加到res列表里，刪除第一行（也就是matrix中的第一個列表），然后逆時針旋轉（這里通過轉置+倒序實現），新的matrix的第一行即為接下來要打印的元素。

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

總結

以上是生活随笔為你收集整理的面试题29. 顺时针打印矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。