螺旋矩阵
#python #dsa

指示

给定m x n矩阵,返回螺旋顺序的矩阵的所有元素。

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

Attempt问题。

方法

  • 输出遵循顺时针运动;我们向左移动,然后向下,向上,最后向右移动。

我们初始化了四个指针;左,右,顶部和底部。
然后从左向右移动,然后更新顶部指针到下一行,因为我们使用给定的行完成了。

然后从当前的顶部到底部移动到最右列上的元素并更新正确的指针。

从最底部向左移动最底部,然后更新底部指针。

从下到顶部并更新左指针。
这个过程一直持续到左右指针相遇或顶部和底部指针相遇。

执行

def spiralOrder(matrix):
    left, right = 0, len(matrix[0])
    top, bottom = 0, len(matrix)

    spiral = []

    while (top < bottom and left < right):
        # left to right
        for i in range(left, right):  
            spiral.append(matrix[top][i])  
        top += 1
        # right to bottom
        for i in range(top, bottom):  # does not repeat value because we have updated top
            spiral.append(matrix[i][right-1])
        right -= 1
        if not (top < bottom and left < right):
            break
        # right to left
        for i in range(right-1, left-1, -1):
            spiral.append(matrix[bottom-1][i])
        bottom -= 1
        # top to bottom
        for i in range(bottom-1, top-1, -1): 
            spiral.append(matrix[i][left])
        left +=1

    return spiral

快乐学习!

参考

Spiral Matrix