算法题--将二维矩阵按顺时针转移元素到一维列表

image.png

0. 链接

题目链接

1. 题目

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

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

Example 2:

Input:
[
  [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]

2. 思路1：模拟NPC按方向走格子

记 i, j分别为matrix的行号和列号

设定
i增加对应从上到下, j增加对应从左到右

则初始位置为(0, 0)

记录 矩阵的最左、最右、最上、最下的下标分别为

left = 0
right = len(matrix[0]) - 1
up = 0
bottom = len(matrix) - 1

矩阵尚未遍历到的部分的宽度和高度分别记录为

width = right - left + 1
height = bottom - up + 1

则初始方向为DIRECT_RIGHT

如果把沿着某个方向行走视为一个个状态的话，则行走的过程，对应一个状态机，基本走法就是

向右 --> 向下 --> 向左 --> 向上 --> 向右

具体过程如下:

• 向右行走:

  • 当尚未抵达最右端时: 即 j < right,只需要增加j,然后收集行走到的格子的值到结果列表
  • 当抵达最右端时, 则需要改变方向向下行走，转向的同时增加up值, 并减少可用高度height

• 向下行走：

  • 当尚未抵达最下端时: 即 i < bottom,只需要增加i,然后收集行走到的格子的值到结果列表
  • 当抵达最下端时, 则需要改变方向向左行走，转向的同时减小right值, 并减少可用宽度width

• 向左行走：

  • 当尚未抵达最左端时: 即 j > left,只需要减少j,然后收集行走到的格子的值到结果列表
  • 当抵达最左端时, 则需要改变方向向上行走，转向的同时减小bottom值, 并减少可用高度height

• 向上行走：

  • 当尚未抵达最上端时: 即 i > up,只需要减少i,然后收集行走到的格子的值到结果列表
  • 当抵达最上端时, 则需要改变方向向右行走，转向的同时增加left值, 并减少可用宽度width

最终，当可用宽度或者可用高度变为0时，行走终止, 表示走完了所有格子。

3. 代码

# coding:utf8
from typing import List


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix) == 0:
            return list()

        DIRECTION_RIGHT = 1
        DIRECTION_DOWN = 2
        DIRECTION_LEFT = 3
        DIRECTION_UP = 4

        left = 0
        right = len(matrix[0]) - 1
        up = 0
        bottom = len(matrix) - 1
        width = right - left + 1
        height = bottom - up + 1

        rtn_array = list()
        i = 0
        j = 0
        rtn_array.append(matrix[i][j])
        direction = DIRECTION_RIGHT
        while width > 0 and height > 0:
            if direction == DIRECTION_RIGHT:
                if j < right:
                    j += 1
                    rtn_array.append(matrix[i][j])
                else:
                    direction = DIRECTION_DOWN
                    up += 1
                    height -= 1
            elif direction == DIRECTION_DOWN:
                if i < bottom:
                    i += 1
                    rtn_array.append(matrix[i][j])
                else:
                    direction = DIRECTION_LEFT
                    right -= 1
                    width -= 1
            elif direction == DIRECTION_LEFT:
                if j > left:
                    j -= 1
                    rtn_array.append(matrix[i][j])
                else:
                    direction = DIRECTION_UP
                    bottom -= 1
                    height -= 1
            elif direction == DIRECTION_UP:
                if i > up:
                    i -= 1
                    rtn_array.append(matrix[i][j])
                else:
                    direction = DIRECTION_RIGHT
                    left += 1
                    width -= 1

        return rtn_array


solution = Solution()
print(solution.spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
print(solution.spiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]))
print(solution.spiralOrder([]))

输出结果

[1, 2, 3, 6, 9, 8, 7, 4, 5]
[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
[]

4. 结果

image.png