前些日子被叫去创新工场面试，经一番面试，面试知道我工程能力较强，算法比较差，就问了我一个算法题：输出螺旋矩阵。哎，这个题以前做过，有大致的想法，但是战场上就是写不出来。悲剧了，今天知道没戏了。

一、定义

螺旋矩阵是什么？

什么是螺旋矩阵？以n=4为例，其输出结果为：

  1   2   3     4

 12  13  14  5

 11  16  15  6

 10   9   8    7        

也即，       

 

看了上图，大致知道什么是螺旋矩阵了？

 

二、实现代码

 

1 int** Matrix(int n) 2 { 3     int** matrix; 4     matrix = new int*[n]; 5     int i =0,j =0,sum = 1; 6     int direction = 0; 7     int level = 0; 8     int all = n*n; 9     for (i = 0; i < n; i++)10     {11         matrix[i] = new int[n];12     }13 14     for (i = 0; i < n; i++)15     {16         for ( j = 0; j < n; j++)17         {18             matrix[i][j] = all;19         }20     }21     22     while(true)23     {        24         25         level += direction/ 4;26         direction = direction % 4;27         if(sum == all+1 )28         {29             break;            30         }31 32         switch (direction)33         {34             case 0:35                 if(n%2 && level == n/2)36                 {37                     matrix[level][level] =sum++;38                 }39                 else40                 {41                     for (j = level; j < n-(level + 1); j++)42                     {43                         matrix[level][j] = sum++;                            44                     }45                 }                46                 direction ++;                47                 break;48             case 1:49                 for (j = level ; j < n-level - 1; j++)50                 {51                     matrix[j][n-level -1] = sum++;52                 }53                 direction++;54             55                 break;56             case 2:57                 for (j = n- level - 1 ; j > level; j--)58                 {59                     matrix[n-level -1][j] = sum++;60                 }61                 direction++;62         63                 break;64             case 3:65                 for (j = n-level - 1 ; j > level; j--)66                 {67                     matrix[j][level] = sum++;68                 }69                 direction++;            70                 break;71         default:72             break;73         }        74     }75     return matrix;76 }

 

三、运行结果

刚测试的偶数没有问题，但是奇数有的问题，所以n*n在矩阵中是没有的，求大神解释和解决。

偶数结果：

 

奇数

 

实际了呢？

 

 

 附上递归方法：

1 void FillMatrix(int** matrix,int n,int level,int sum); 2 int** Matrix2(int n) 3 { 4     int** matrix; 5     matrix = new int*[n]; 6     int i =0,j =0;     7     for (i = 0; i < n; i++) 8     { 9         matrix[i] = new int[n];10     }11 12     for (i = 0; i < n; i++)13     {14         for ( j = 0; j < n; j++)15         {16             matrix[i][j] = 0;17         }18     }19 20     FillMatrix(matrix,n,0,1);21     return matrix;22 }23 24 void FillMatrix(int** matrix,int n,int level,int sum)25 {26     int j = 0;27     if(n%2 && level == n/2)28     {29         matrix[level][level] = sum++;30         return;31     }32     if(sum == n*n+1)33     {34         return;35     }36 37     for (j = level; j < n - level - 1; j++)38     {39         matrix[level][j] = sum++;40     }41 42     for (j = level; j < n - level - 1; j++)43     {44         matrix[j][n-level-1] = sum++;45     }46 47     for (j = n - level - 1; j > level; j--)48     {49         matrix[n - level - 1][j] = sum++;50     }51 52     for (j = n - level - 1; j > level; j--)53     {54         matrix[j][level] = sum++;55     }56 57     return FillMatrix(matrix,n,level+1,sum);58 }