首页 > 代码库 > [Leetcode] spiral matrix 螺旋矩阵

[Leetcode] spiral matrix 螺旋矩阵

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

For example,
Given the following matrix:

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

You should return[1,2,3,6,9,8,7,4,5].

 题意:以螺旋的方式,顺时针访问数组。

思路:按照遍历的方向来不停的结果中压入值:左到右、上到下、右到左、下到上......一圈圈的向内访问。这里的难点有两处,一、圈与圈之间的过渡;二、若最后,只剩一行或者一列怎么办。针对第一个问题,我们可以定义四个变量,分别代表左右、上下,按照访问的顺序存入值。针对第二问题,若只剩一列,我们从上到下访问,并返回结果,只剩一行时,同理。还有一个问题是,访问时,变量 i 的取值范围。这可以按如下的方式取值,即,访问方向上,行或列的最后一个留个下一个循环去访问。

技术分享

代码如下:

 1 class Solution {
 2 public:
 3     vector<int> spiralOrder(vector<vector<int> > &matrix) 
 4     {
 5         vector<int> res;
 6         if(matrix.size()==0||matrix[0].size()==0)   return res;
 7 
 8         int left=0,right=matrix[0].size()-1;
 9         int up=0,down=matrix.size()-1;
10 
11         while(right>=left && down>=up)
12         {
13             if(right==left)     //单列
14             {
15                 for(int i=up;i<=down;++i)
16                 {
17                     res.push_back(matrix[i][right]);
18                 }
19                 return res;
20             }
21             else if(up==down)   //单行
22             {
23                 for(int i=left;i<=right;++i)
24                 {
25                     res.push_back(matrix[up][i]);
26                 }
27                 return res;
28             }
29 
30             for(int i=left;i<right;++i)     //左到右
31                 res.push_back(matrix[up][i]);
32 
33             for(int i=up;i<down;++i)        //上到下
34                 res.push_back(matrix[i][right]);
35 
36             for(int i=right;i>left;i--)     //右到左
37                 res.push_back(matrix[down][i]);
38 
39             for(int i=down;i>up;i--)        //下到上
40                 res.push_back(matrix[i][left]);
41             
42             up++;
43             left++;
44             down--;
45             right--;
46         }    
47         return res;
48     }
49 };

 

[Leetcode] spiral matrix 螺旋矩阵