LeetCode 54 Spiral Matrix 解题思路和python代码

题目：
Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

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

题目解析：
这道题目要求我们遍历 matrix 中的每个元素，用一个螺旋形的顺序。我们需要从外层到内层，遍历 matrix 中的每个元素。
我们会使用以下4个指针。
top: 从0开始，指向 matrix 的第一行。
bottom: 从 m-1 开始，指向 matrix 的最后一行。
left: 从0开始，指向 matrix 的第一列。
right: 从 n-1 开始，指向matix 的最后一列。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        result = []
        if not matrix:
            return result
        
        top, bottom = 0, len(matrix)-1
        left, right = 0, len(matrix[0]) - 1

        while top <= bottom and left <= right:
            # Traverse from left to right across the top row
            for i in range(left, right+1):
                result.append(matrix[top][i])
            top += 1

            # Traverse down the right column
            for i in range(top, bottom+1):
                result.append(matrix[i][right])
            right -= 1

            if top <= bottom:
                # Traverse from right to left across the bottom row
                for i in range(right, left-1, -1):
                    result.append(matrix[bottom][i])
                bottom -= 1
            
            if left <=  right:
                # Traverse up the left column
                for i in range(bottom, top-1, -1):
                    result.append(matrix[i][left])
                left += 1
        
        return result


        

从4个方向进行遍历：
从 matrix 的第一行，也就是顶部，从左到右，把元素添加进 result。
接着，从 matrix的最后一列，也就是最右边，从上到下，把元素添加进 result。
然后，从 matrix的最后一行，也就是底部，从右到左，把元素添加进result。
最后，从 matrix的第一列，也就是最左边，从下到上，把元素添加进result。

重复以上步骤，从外到内，直到把虽有元素添加完毕。

Time Complexity 是 O(m*n)，其中m是行数，n是列数。

原文地址：https://blog.csdn.net/weixin_57266891/article/details/142738463

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！