54.Spiral Matrix

tags: Medium,Array,Matrix

54. Spiral Matrix

題目描述

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

解答

Javascript

思路：每次都把第一排拿出來，然後逆時針旋轉90度，重複到拿完為止。

function spiralOrder(matrix) {
  const result = [];
  while (matrix.length > 0) {
    result.push(...matrix.shift());
    if (matrix.length > 0) {
      matrix = rotate(matrix);
    }
  }

  return result;
}

// 逆時針旋轉90度
function rotate(matrix) {
  const newMatrix = [];
  const yLength = matrix.length;
  const xLength = matrix[0].length;
  for (let y = 0; y < xLength; y++) {
    newMatrix[y] = [];
  }

  for (let y = 0; y < yLength; y++) {
    for (let x = 0; x < xLength; x++) {
      const length = matrix[y].length;
      const rX = y;
      const rY = length - 1 - x;
      newMatrix[rY][rX] = matrix[y][x];
    }
  }

  return newMatrix;
}

MarsgoatMay 9, 2023

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        d = 0
        sx, sy = 0, 0
        res = [matrix[0][0]]
        VISITED = 101
        matrix[0][0] = VISITED

        while len(res) < m * n:
            dx, dy = directions[d % 4]
            nx, ny = sx + dx, sy + dy

            if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] != VISITED:
                res.append(matrix[nx][ny])
                matrix[nx][ny] = VISITED
                sx, sy = nx, ny
            else:
                d += 1

        return res

Ron ChenTue, May 9, 2023

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        return matrix and matrix[0] + self.spiralOrder(list(map(list, reversed(list(zip(*matrix[1:]))))))

Yen-Chi ChenTue, May 9, 2023

Reference

回到題目列表