LeetCode --- 54. Spiral Matrix

タイトルリンク: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].
この問題の要求は,与えられたm*nの行列であり,すべての要素(時計回り)を螺旋順に返すことである.
単純な配列操作の問題は、右、下、左、上の順に配列を行または列ごとに巡回するだけです.ただし、現在[x,y]の位置にあると仮定する境界問題に注意してください.
右に遍歴すると、xは変わらないため、yは毎回1を加えるので、yはn-xより小さくすればよい.
下へ遍歴すると、yは変わらないため、xは毎回1を加えるので、xはm-(n-y-1)より小さいことが要求される.
左に遍歴すると、xは変わらないため、yは毎回1を減らすので、yがm-x-1より小さくなければよい.
上遍歴では,yは変わらないため,xは毎回1を減らすので,xがy+1より小さくなければよい.
時間複雑度:O(mn)
空間複雑度:O(mn)

 1 class Solution
 2 {
 3 public:
 4     vector<int> spiralOrder(vector<vector<int> > &matrix)
 5     {
 6         vector<int> vi;
 7         
 8         if(matrix.size() == 0)
 9             return vi;
10         
11         int m = matrix.size(), n = matrix[0].size();
12         int x = 0, y = 0, mn = m * n - 1;
13         vi.push_back(matrix[x][y]);
14         
15         while(mn > 0)
16         {
17             while(y + 1 < n - x && mn -- > 0)
18                 vi.push_back(matrix[x][++ y]);
19             
20             while(x + 1 < m - (n - y - 1) && mn -- > 0)
21                 vi.push_back(matrix[++ x][y]);
22             
23             while(y - 1 >= m - x - 1 && mn -- > 0)
24                 vi.push_back(matrix[x][-- y]);
25             
26             while(x - 1 >= y + 1 && mn -- > 0)
27                 vi.push_back(matrix[-- x][y]);
28         }
29         
30         return vi;
31     }
32 };

転載は出典:LeetCode---54.Spiral Matrix