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的刷题之旅中取得更多进步！