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].

[解题思路]

递归式剥皮。首先剥掉最外面一层，然后递归调用剥剩余部分。 需要注意的是处理row_len和col_len为1 的情况。

这题主要是实现的难度，坐标的计算比较繁琐，算法上没有难度。

[Code]

1:    vector
    
      spiralOrder(vector
     
      
        > &matrix) {  2:      // Start typing your C/C++ solution below  3:      // DO NOT write int main() function      4:      vector
       
         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
        
         
           > &matrix, 13: int row_s, 14: int row_len, 15: int col_s, 16: int col_len, 17: vector
          
           & 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
          
         
        
       
      
     
    

Update 2014/01/05

想了一下，递归的解法看起来还是费劲，尤其是下标的计算，很繁琐。改一下，不用递归，在一个循环里面解决，提高一下可读性。

1 vector
     
       spiralOrder(vector
      
       
         > &matrix) {
    2     vector
        
          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 }