LeetCode如何順時針打印矩陣

LeetCode如何順時針打印矩陣

引言

在算法和數據結構的學習過程中，矩陣操作是一個非常重要的部分。LeetCode作為全球知名的編程題庫，提供了大量與矩陣相關的題目，其中“順時針打印矩陣”是一個經典且具有代表性的問題。本文將詳細探討如何在LeetCode上解決“順時針打印矩陣”的問題，包括問題描述、解題思路、代碼實現以及復雜度分析。

問題描述

題目

給定一個 m x n 的矩陣 matrix，請按照順時針順序，返回矩陣中的所有元素。

示例

示例 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]

提示

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

解題思路

1. 理解問題

首先，我們需要明確“順時針打印矩陣”的含義。順時針打印矩陣意味著我們需要按照從外到內、從左到右、從上到下、從右到左、從下到上的順序依次訪問矩陣中的每一個元素。

2. 分析矩陣的結構

一個 m x n 的矩陣可以看作是由多個“層”組成的。每一層都是一個矩形環，從外到內依次是第1層、第2層，依此類推。每一層的打印順序都是順時針方向。

3. 確定每一層的邊界

為了打印每一層的元素，我們需要確定每一層的邊界。假設當前層的左上角坐標為 (top, left)，右下角坐標為 (bottom, right)，那么：

• 從左到右打印上邊界的元素：(top, left) 到 (top, right)
• 從上到下打印右邊界的元素：(top + 1, right) 到 (bottom, right)
• 如果 bottom > top，則從右到左打印下邊界的元素：(bottom, right - 1) 到 (bottom, left)
• 如果 right > left，則從下到上打印左邊界的元素：(bottom - 1, left) 到 (top + 1, left)

4. 更新邊界

在打印完當前層的所有元素后，我們需要更新邊界，進入下一層：

• top++
• left++
• bottom--
• right--

5. 終止條件

當 top > bottom 或 left > right 時，表示所有層都已打印完畢，算法終止。

代碼實現

Python 實現

def spiralOrder(matrix):
    if not matrix or not matrix[0]:
        return []
    
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    
    while top <= bottom and left <= right:
        # 從左到右打印上邊界
        for i in range(left, right + 1):
            result.append(matrix[top][i])
        top += 1
        
        # 從上到下打印右邊界
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
        
        if top <= bottom:
            # 從右到左打印下邊界
            for i in range(right, left - 1, -1):
                result.append(matrix[bottom][i])
            bottom -= 1
        
        if left <= right:
            # 從下到上打印左邊界
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
    
    return result

代碼解釋

1. 初始化邊界：top 和 left 初始化為 0，bottom 和 right 分別初始化為矩陣的行數和列數減 1。
2. 循環打印每一層：
   • 從左到右打印上邊界。
   • 從上到下打印右邊界。
   • 如果 top <= bottom，則從右到左打印下邊界。
   • 如果 left <= right，則從下到上打印左邊界。
3. 更新邊界：每次打印完一層后，更新邊界，進入下一層。
4. 終止條件：當 top > bottom 或 left > right 時，循環結束。

復雜度分析

時間復雜度

• 每個元素只被訪問一次，因此時間復雜度為 O(m * n)，其中 m 是矩陣的行數，n 是矩陣的列數。

空間復雜度

• 除了存儲結果的列表 result 外，算法只使用了常數個額外空間，因此空間復雜度為 O(1)。

測試用例

測試用例 1

matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(spiralOrder(matrix))  # 輸出: [1,2,3,6,9,8,7,4,5]

測試用例 2

matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
print(spiralOrder(matrix))  # 輸出: [1,2,3,4,8,12,11,10,9,5,6,7]

測試用例 3

matrix = [[1]]
print(spiralOrder(matrix))  # 輸出: [1]

測試用例 4

matrix = [[1,2],[3,4]]
print(spiralOrder(matrix))  # 輸出: [1,2,4,3]

總結

通過本文的詳細講解，我們了解了如何在LeetCode上解決“順時針打印矩陣”的問題。我們從問題描述出發，逐步分析了解題思路，并提供了Python代碼實現。此外，我們還對算法的時間復雜度和空間復雜度進行了分析，并通過多個測試用例驗證了代碼的正確性。

掌握這一問題的解決方法不僅有助于提升編程能力，還能為后續解決更復雜的矩陣相關問題打下堅實的基礎。希望本文能對讀者有所幫助，祝大家在LeetCode的刷題之旅中取得更多進步！