LeetCode54 螺旋矩阵

给你一个m行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]

分析

1.暴力解法：利用已知的行列数循环输出。（时间复杂度高，不推荐）
2.状态表解法：
从示例中可以看出来，输出遵守四个方向，依次是：右，下，左，上。对于数组元素$\text{element}[i][j]$，四种状态分别对应着$j+1$, $i+1$, $j-1$, $i-1$。
那么如何更新状态？有两个限制条件
1)首先是矩阵的长度宽度；2)这个矩阵元素是否被遍历过了；
第二个条件就需要另外开辟一个状态矩阵，初始化为$m\times n$大小的0矩阵，若遍历过，元素状态变为1。

Code

def spiraOrder(matrix):row_num = len(matrix)col_num = len(matrix[0])# state_list = []state_list = [[0 for _ in range(row_num)] for _ in range(col_num)]total_num = row_num * col_numdirection_list = [[0, 1], [1, 0], [0, -1], [-1, 0]]direction_index = 0row, col = 0, 0res_list = []for i in range(total_num):res_list.append(matrix[row][col])state_list[row][col] = 1# print(state_list)next_row = row + direction_list[direction_index][0]next_col = col + direction_list[direction_index][1]if next_row < 0 or next_col < 0 or next_col >= col_num or next_row >= row_num or state_list[next_row][next_col]:direction_index = (direction_index + 1) % 4# print("index: ", direction_index)row += direction_list[direction_index][0]col += direction_list[direction_index][1]return res_list
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]print(spiraOrder(matrix)) # [1, 2, 3, 6, 9, 8, 7, 4, 5]