54.螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出:[1,2,3,6,9,8,7,4,5]
思路
本题解决思路继承自59.螺旋矩阵II，建议看完59.螺旋矩阵II之后再看本题
与59.螺旋矩阵II相同的是：两者都是模拟矩形的顺时针旋转，所以核心依然是依然是坚持循环不变量，按照左闭右开的原则
模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去，如下所示：
这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。
与59.螺旋矩阵II不同的是：前题中的螺旋矩阵是正方形，只有正方形的边长n一个边界条件，而本题中，需要考虑长方形的长和宽(m行和n列)两个边界条件。自然，m可以等于n，即前题可视为本题在m==n的特殊情况。
我们从最一般的情况开始考虑，与59.螺旋矩阵II题解对比起来，m和n的带入，主要引来两方面的差异：
- loop的计算：
本题的loop计算与59.螺旋矩阵II算法略微差异，因为存在rows和columns两个维度，可自行分析，loop只能取min(rows, columns)，例如rows = 5, columns = 7，那loop = 5 / 7 = 2 - mid的计算及填充：
1、同样的原理，本题的mid计算也存在上述差异；
2、
如果min(rows, columns)为偶数，则不需要在最后单独考虑矩阵最中间位置的赋值
如果min(rows, columns)为奇数，则矩阵最中间位置不只是[mid][mid],而是会留下来一个特殊的中间行或者中间列，具体是中间行还是中间列，要看rows和columns的大小，如果rows > columns,则是中间列，相反，则是中间行
代码如下，已经详细注释了每一步的目的，可以看出while循环里判断的情况是很多的，代码里处理的原则也是统一的左闭右开。
整体C++代码如下：
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0)
return {};
int rows = matrix.size(), columns = matrix[0].size();
int total = rows * columns;
vector<int> res(total); // 使用vector定义一个一维数组存放结果
int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
int loop = min(rows, columns) / 2;
// 本题的loop计算与59.螺旋矩阵II算法略微差异，因为存在rows和columns两个维度，可自行分析，loop只能取min(rows, columns)，例如rows = 5, columns = 7，那loop = 5 / 7 = 2
int mid = min(rows, columns) / 2;
// 1、同样的原理，本题的mid计算也存在上述差异；
// 2、
//如果min(rows, columns)为偶数，则不需要在最后单独考虑矩阵最中间位置的赋值
//如果min(rows, columns)为奇数，则矩阵最中间位置不只是[mid][mid],而是会留下来一个特殊的中间行或者中间列，具体是中间行还是中间列，要看rows和columns的大小，如果rows > columns,则是中间列，相反，则是中间行
//相信这一点不好理解，建议自行画图理解
int count = 0;// 用来给矩阵中每一个空格赋值
int offset = 1;// 每一圈循环，需要控制每一条边遍历的长度
int i,j;
while (loop --) {
i = startx;
j = starty;
// 下面开始的四个for就是模拟转了一圈
// 模拟填充上行从左到右(左闭右开)
for (j = starty; j < starty + columns - offset; j++) {
res[count++] = matrix[startx][j];
}
// 模拟填充右列从上到下(左闭右开)
for (i = startx; i < startx + rows - offset; i++) {
res[count++] = matrix[i][j];
}
// 模拟填充下行从右到左(左闭右开)
for (; j > starty; j--) {
res[count++] = matrix[i][j];
}
// 模拟填充左列从下到上(左闭右开)
for (; i > startx; i--) {
res[count++] = matrix[i][starty];
}
// 第二圈开始的时候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
startx++;
starty++;
// offset 控制每一圈里每一条边遍历的长度
offset += 2;
}
// 如果min(rows, columns)为奇数的话，需要单独给矩阵最中间的位置赋值
if (min(rows, columns) % 2) {
if(rows > columns){
for (int i = mid; i < mid + rows - columns + 1; ++i) {
res[count++] = matrix[i][mid];
}
} else {
for (int i = mid; i < mid + columns - rows + 1; ++i) {
res[count++] = matrix[mid][i];
}
}
}
return res;
}
};
类似题目
其他语言版本
Java
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
//存放数组的数
List<Integer> ans = new ArrayList<>();
//列数
int columns = matrix[0].length;
//行数
int rows = matrix.length;
//遍历起点
int start = 0;
//循环的次数 行数和列数中的最小值除以二
int loop = Math.min(rows,columns) / 2;
//未遍历的中间列（行）的列（行）下标
int mid = loop;
//终止条件
int offSet = 1;
int i,j;
while(loop-- > 0) {
//初始化起点
i = j = start;
//从左往右
for(; j < columns - offSet; j++)
ans.add(matrix[i][j]);
//从上往下
for(; i < rows - offSet; i++)
ans.add(matrix[i][j]);
//从右往左
for(; j > start; j--)
ans.add(matrix[i][j]);
//从下往上
for(; i > start; i--)
ans.add(matrix[i][j]);
//每循环一次 改变起点位置
start++;
//终止条件改变
offSet++;
}
//如果行和列中的最小值是奇数 则会产生中间行或者中间列没有遍历
if(Math.min(rows,columns) % 2 != 0) {
//行大于列则产生中间列
if(rows > columns) {
//中间列的行的最大下标的下一位的下标为mid + rows - columns + 1
for(int k = mid; k < mid + rows - columns + 1; k++) {
ans.add(matrix[k][mid]);
}
}else {//列大于等于行则产生中间行
//中间行的列的最大下标的下一位的下标为mid + columns - rows + 1
for(int k = mid; k < mid + columns - rows + 1; k++) {
ans.add(matrix[mid][k]);
}
}
}
return ans;
}
}
Javascript
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function(matrix) {
let m = matrix.length
let n = matrix[0].length
let startX = startY = 0
let i = 0
let arr = new Array(m*n).fill(0)
let offset = 1
let loop = mid = Math.floor(Math.min(m,n) / 2)
while (loop--) {
let row = startX
let col = startY
// -->
for (; col < n + startY - offset; col++) {
arr[i++] = matrix[row][col]
}
// down
for (; row < m + startX - offset; row++) {
arr[i++] = matrix[row][col]
}
// <--
for (; col > startY; col--) {
arr[i++] = matrix[row][col]
}
for (; row > startX; row--) {
arr[i++] = matrix[row][col]
}
startX++
startY++
offset += 2
}
if (Math.min(m, n) % 2 === 1) {
if (n > m) {
for (let j = mid; j < mid + n - m + 1; j++) {
arr[i++] = matrix[mid][j]
}
} else {
for (let j = mid; j < mid + m - n + 1; j++) {
arr[i++] = matrix[j][mid]
}
}
}
return arr
};
Python
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if len(matrix) == 0 or len(matrix[0]) == 0 : # 判定List是否为空
return []
row, col = len(matrix), len(matrix[0]) # 行数，列数
loop = min(row, col) // 2 # 循环轮数
stx, sty = 0, 0 # 起始x，y坐标
i, j =0, 0
count = 0 # 计数
offset = 1 # 每轮减少的格子数
result = [0] * (row * col)
while loop>0 :# 左闭右开
i, j = stx, sty
while j < col - offset : # 从左到右
result[count] = matrix[i][j]
count += 1
j += 1
while i < row - offset : # 从上到下
result[count] = matrix[i][j]
count += 1
i += 1
while j>sty : # 从右到左
result[count] = matrix[i][j]
count += 1
j -= 1
while i>stx : # 从下到上
result[count] = matrix[i][j]
count += 1
i -= 1
stx += 1
sty += 1
offset += 1
loop -= 1
if min(row, col) % 2 == 1 : # 判定是否需要填充多出来的一行
i = stx
if row < col :
while i < stx + col - row + 1 :
result[count] = matrix[stx][i]
count += 1
i += 1
else :
while i < stx + row - col + 1 :
result[count] = matrix[i][stx]
count += 1
i += 1
return result
版本二：定义四个边界
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if not matrix:
return []
rows = len(matrix)
cols = len(matrix[0])
top, bottom, left, right = 0, rows - 1, 0, cols - 1
print_list = []
while top <= bottom and left <= right:
# 从左到右
for i in range(left, right + 1):
print_list.append(matrix[top][i])
top += 1
# 从上到下
for i in range(top, bottom + 1):
print_list.append(matrix[i][right])
right -= 1
# 从右到左
if top <= bottom:
for i in range(right, left - 1, -1):
print_list.append(matrix[bottom][i])
bottom -= 1
# 从下到上
if left <= right:
for i in range(bottom, top - 1, -1):
print_list.append(matrix[i][left])
left += 1
return print_list