題目敘述
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.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
Hint 1:
Well for some problems, the best way really is to come up with some algorithms for simulation. Basically, you need to simulate what the problem asks us to do.
Hint 2:
We go boundary by boundary and move inwards. That is the essential operation. First row, last column, last row, first column and then we move inwards by 1 and then repeat. That's all, that is all the simulation that we need.
Hint 3:
Think about when you want to switch the progress on one of the indexes. If you progress on i out of [i, j], you'd be shifting in the same column. Similarly, by changing values for j, you'd be shifting in the same row. Also, keep track of the end of a boundary so that you can move inwards and then keep repeating. It's always best to run the simulation on edge cases like a single column or a single row to see if anything breaks or not.
題目翻譯
題目很簡單，會給一個 m x n 的 matrix 矩陣，然後依照螺旋順序回傳所有的元素
解法解析
這題的解法是用了設定了邊界的方式，慢慢的縮小。可以看到範例 Python 中就是先定義了，四個方向的初始值。依序的處理了，往右、往下、往左、往上，走完一圈後，將邊界縮小。重複此動作將全部元素走完。
解法範例
Go
func spiralOrder(matrix [][]int) []int {
ordered := append([]int{}, matrix[0]...)
m, n := len(matrix), len(matrix[0])
total := m * n
dir, pos, movement := 0, []int{0, n - 1}, [][]int{{1, 0}, {0, -1}, {-1, 0}, {0, 1}}
for len(ordered) < total {
for i := 1; i < m; i++ {
pos[0] += movement[dir][0]
pos[1] += movement[dir][1]
ordered = append(ordered, matrix[pos[0]][pos[1]])
}
m--
m, n = n, m
dir = (dir + 1) % 4
}
return ordered
JavaScript
var spiralOrder = function (matrix) {
const result = [];
const rows = matrix.length, columns = matrix[0].length;
let up = 0, left = 0;
let right = columns - 1;
let down = rows - 1;
while (result.length < rows * columns) {
for (let col = left; col <= right; col++) {
result.push(matrix[up][col]);
}
for (let row = up + 1; row <= down; row++) {
result.push(matrix[row][right]);
}
if (up !== down) {
for (let col = right - 1; left - 1 < col; col--) {
result.push(matrix[down][col]);
}
}
if (left !== right) {
for (let row = down - 1; up < row; row--) {
result.push(matrix[row][left]);
}
}
left++;
right--;
up++;
down--;
}
return result;
}
Kotlin
class Solution {
fun spiralOrder(matrix: Array<IntArray>): List<Int> {
val order = mutableListOf<Int>()
if (matrix.isEmpty()) {
return order
}
var startRow = 0
var endRow = matrix.size - 1
var startColumn = 0
var endColumn = matrix[0].size - 1
while (startRow <= endRow && startColumn <= endColumn) {
for (column in startColumn..endColumn) {
order.add(matrix[startRow][column])
}
for (row in startRow + 1..endRow) {
order.add(matrix[row][endColumn])
}
for (column in endColumn - 1 downTo startColumn) {
if (startRow == endRow) break
order.add(matrix[endRow][column])
}
for (row in endRow - 1 downTo startRow + 1) {
if (startColumn == endColumn) break
order.add(matrix[row][startColumn])
}
startRow++
endRow--
startColumn++
endColumn--
}
return order
}
}
PHP
Python
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
result = []
rows, columns = len(matrix), len(matrix[0])
up = left = 0
right = columns - 1
down = rows - 1
while len(result) < rows * columns:
for col in range(left, right + 1):
result.append(matrix[up][col])
for row in range(up + 1, down + 1):
result.append(matrix[row][right])
if up != down:
for col in range(right - 1, left - 1, -1):
result.append(matrix[down][col])
if left != right:
for row in range(down - 1, up, -1):
result.append(matrix[row][left])
left += 1
right -= 1
up += 1
down -= 1
return result
Rust
Swift
class Solution {
func spiralOrder(_ matrix: [[Int]]) -> [Int] {
guard !matrix.isEmpty else {
return []
}
var top = 0
var bottom = matrix.count - 1
var left = 0
var right = matrix[0].count - 1
let count = matrix.count * matrix[0].count
var arr = [Int]()
while arr.count < count {
for i in stride(from: left, to: right+1, by: 1) where arr.count < count {
arr.append(matrix[top][i])
}
top += 1
for i in stride(from: top, to: bottom+1, by: 1) where arr.count < count {
arr.append(matrix[i][right])
}
right -= 1
for i in stride(from: right, to: left-1, by: -1) where arr.count < count {
arr.append(matrix[bottom][i])
}
bottom -= 1
for i in stride(from: bottom, to: top-1, by: -1) where arr.count < count {
arr.append(matrix[i][left])
}
left += 1
}
return arr
}
}