LeetCode 54 - Spiral Matrix

作者 QIFAN 日期 2017-01-17
LeetCode 54 - Spiral Matrix

原题链接: 54. Spiral Matrix


题干

给定一个 M * N 的矩阵,返回从外围顺时针旋转遍历的结果。

举例
输入:

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

输出:[1,2,3,6,9,8,7,4,5]

思路

有两个关键的变量,方向和已遍历的厚度。方向 direction 指遍历的方向,包括上、下、左、右,我分别用 0 、 1、 2 、 3 来表示。厚度 borderLength 是指对于某条边, 0 ~ borderLengthborderLength ~ length 已经遍历过,直接 skip 。

通过观察,发现在每轮转圈的最后一条边,也就是 direction = 3 时, borderLength 会增加。

遍历停止的条件一种是数数,当 num == m * n 时停止遍历。另一种是当走到了边界里面,说明已经无路可走了。

时间复杂度为 $O(n^2)$ 。

代码:

public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
int M = matrix.length;
if (M == 0) {
return res;
}
int N = matrix[0].length;
int direction = 0;
int borderLength = 0;
int row = 0;
int col = 0;
// 当走进边界,遍历停止。
while (row >= borderLength && col >= borderLength && row + borderLength < M && col + borderLength < N) {
if (direction == 0) {
for (; col < N - borderLength; col++) {
res.add(matrix[row][col]);
}
// 此时 col 超出边界,row 这一行已经遍历完。后面的同理。
row++;
col--;
} else if (direction == 1) {
for (; row < M - borderLength; row++) {
res.add(matrix[row][col]);
}
col--;
row--;
} else if (direction == 2) {
for (; col >= borderLength; col--) {
res.add(matrix[row][col]);
}
row--;
col++;
} else {
for (; row > borderLength; row--) {
res.add(matrix[row][col]);
}
row++;
col++;
borderLength++;
}
// 转向
direction = (direction + 1) % 4;
}
return res;
}