LeetCode54. Spiral Matrix

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

Example 1:

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

Example 2:

1
2
3
4
5
6
7
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]

思路

  • add the elements in the spiral order
    1. top row
    2. right col
    3. bottom row
    4. left col
  • finishing a row/col,update the variable, break check

My code in C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty())
return{ };
int rows = matrix.size();
int cols = matrix[0].size();
vector<int> sprial;
int top = 0, right = cols - 1, bottom = rows - 1, left = 0;
while (sprial.size()<cols*rows)
{
//top row:left to right
for (int col = left; col <= right; col++)
sprial.push_back(matrix[top][col]);
if (++top > bottom) break;

//right col: top to bottom
for (int row = top; row <= bottom; row++)
sprial.push_back(matrix[row][right]);
if (--right < left) break;

//bottom row: right to left
for (int col = right; col >= left; col--)
sprial.push_back(matrix[bottom][col]);
if (--bottom < top) break;//1.这里是<

//left col: bottom to top
for (int row = bottom; row >= top; row--)
//2.row>=top不是<=容易弄错!!
sprial.push_back(matrix[row][left]);
if (++left > right) break;
}

return sprial;
}

细节

  1. 每次判断越界的大于小于容易弄错,尤其注意bottom的坐标应该是大于top的。

总结

将矩阵以螺旋顺序放入容器中,用上下左右四个变量表示矩阵的边界,依次沿着上右下左的边界循环打印,打印完一行或者一列边界后,更新边界变量并作越界检查,越界就break。

Thanks for Support.