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].
» Solve this problem
[解题思路]
递归式剥皮。首先剥掉最外面一层，然后递归调用剥剩余部分。 需要注意的是处理row_len和col_len为1 的情况。
这题主要是实现的难度，坐标的计算比较繁琐，算法上没有难度。
[Code]
1: vector<int> spiralOrder(vector<vector<int> > &matrix) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: vector<int> output;
5: int row_len = matrix.size();
6: if(row_len ==0) return output;
7: int col_len = matrix[0].size();
8: print_order(matrix, 0, row_len, 0, col_len, output);
9: return output;
10: }
11: void print_order(
12: vector<vector<int> > &matrix,
13: int row_s,
14: int row_len,
15: int col_s,
16: int col_len,
17: vector<int>& output)
18: {
19: if(row_len<=0 || col_len <=0) return;
20: if(row_len ==1)
21: {
22: for(int i =col_s; i< col_s+col_len; i++)
23: output.push_back(matrix[row_s][i]);
24: return;
25: }
26: if(col_len ==1)
27: {
28: for(int i =row_s; i<row_s + row_len; i++)
29: output.push_back(matrix[i][col_s]);
30: return;
31: }
32: for(int i =col_s; i<col_s+col_len-1; i++) //up
33: output.push_back(matrix[row_s][i]);
34: for(int i =row_s; i<row_s+row_len-1; i++) //right
35: output.push_back(matrix[i][col_s+col_len-1]);
36: for(int i =col_s; i<col_s+col_len-1; i++) //bottom
37: output.push_back(matrix[row_s+row_len-1][2*col_s+ col_len-1 -i]);
38: for(int i =row_s; i<row_s+row_len-1; i++) //left
39: output.push_back(matrix[2*row_s+row_len-1-i][col_s]);
40: print_order(matrix, row_s+1, row_len-2, col_s+1, col_len-2, output);
41: }
Update 2014/01/05
想了一下，递归的解法看起来还是费劲，尤其是下标的计算，很繁琐。改一下，不用递归，在一个循环里面解决，提高一下可读性。
1 vector<int> spiralOrder(vector<vector<int> > &matrix) {
2 vector<int> result;
3 int row = matrix.size();
4 if(row == 0) return result;
5 int col = matrix[0].size();
6 if(col == 0) return result;
7
8 //define the step for 4 directions
9 int x[4] = { 1, 0, -1, 0 };
10 int y[4] = { 0, 1, 0, -1 };
11
12 int visitedRows = 0;
13 int visitedCols = 0;
14
15 // define direction: 0 means up, 1 means down, 2 means left, 3 means up
16 int direction = 0;
17 int startx = 0, starty = 0;
18 int candidateNum = 0, moveStep = 0;
19 while (true)
20 {
21 if (x[direction] == 0) // visit y axis
22 candidateNum = row - visitedRows;
23 else // visit x axis
24 candidateNum = col - visitedCols;
25
26 if (candidateNum <= 0)
27 break;
28 result.push_back(matrix[starty][startx]);
29 moveStep++;
30 if (candidateNum == moveStep) // change direction
31 {
32 visitedRows += x[direction] == 0 ? 0 : 1;
33 visitedCols += y[direction] == 0 ? 0 : 1;
34 direction = (direction + 1) % 4;
35 moveStep = 0;
36 }
37 startx += x[direction];
38 starty += y[direction];
39 }
40 return result;
41 }
