记得这是大二时，我的老师给我出的题，回去琢磨了半天，感觉不是很难。今天整理电脑里的资料时发现了，拿出来看看，上网搜搜发现面试题里挺多的，但网上的看起来比我的复杂得多（也许是个人感觉，我比较另类），所以拿出来分享。时间复杂度基本上就是O(N^2)了。
这个螺旋矩阵有几类，我当时拿到的题是从中间往外顺时针旋转，如下所示：
7 8 9
6 1 2
5 4 3
这个太小不好分析规律，来个大的：
看出规律没？找张草稿纸研究研究。
我当时是这么想的：
红线方程y=x，绿线方程y=-x+4，4为矩形边长。
两条直线将区域分为四个部分，划分好每个区域的边界值，每个区域的坐标变化规律有四种，x++，y++，x--，y--，接下来仔细分析就能得到算法：
void SpiralArray(int size, int** ar)
{
int a=size/2*2+1;//保证边长为奇数
int y=a/2,x=a/2;//从中心点开始
for (int i=1;i<=size*size;i++)//(int i=size*size;i>=1;i--)
{
if (x<=a-y-1&&x>=y)
{
ar[y][x]=i;
x++;
}
else if (x>a-y-1&&x>y)
{
ar[y][x]=i;
y++;
}
else if (x>a-y-1&&x<=y)
{
ar[y][x]=i;
x--;
}
else if (x<=a-y-1&&x<y)
{
ar[y][x]=i;
y--;
}
}
}
应该看得懂吧，下面是完整代码：
#include<iostream>
#include<time.h>
using namespace std;
void SpiralArray(int size, int** ar)
{
int a=size/2*2+1;//保证边长为奇数
int y=a/2,x=a/2;//从中心点开始
for (int i=1;i<=size*size;i++)//(int i=size*size;i>=1;i--)
{
if (x<=a-y-1&&x>=y)
{
ar[y][x]=i;
x++;
}
else if (x>a-y-1&&x>y)
{
ar[y][x]=i;
y++;
}
else if (x>a-y-1&&x<=y)
{
ar[y][x]=i;
x--;
}
else if (x<=a-y-1&&x<y)
{
ar[y][x]=i;
y--;
}
}
}
int main()
{
int n;
do
{
cout<<"Please input a number(\"0\" is exit):";
cin>>n;
if (n==0)break;
int a=n/2*2+1;//保证边长为奇数
int **g=new int *[a];
for (int i=0;i<a;i++)
g[i]=new int[a];
for (int p=0;p<a;p++)
for (int q=0;q<a;q++)
g[p][q]=0;
clock_t start,finish;
start = clock();
SpiralArray(n, g);
finish = clock();
double duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "%f seconds\n", duration );
char c;
cout<<"Output ?(y/n):";
cin>>c;
if ('n'==c)continue;
int ws=2;
if (n*n/100>=1)
ws=4;
else if (n*n/10>=1)
ws=3;
for (int y=0;y<a;y++)
{
for (int x=0;x<a;x++)
{
if (g[y][x]==0)
{
cout.width(ws);
cout<<' ';
}
else
{
cout.width(ws);
cout<<g[y][x];
}
}
cout<<endl;
}
for (i=0;i<a;i++)
{
delete[a] g[i];
g[i]=NULL;
}
delete[a] g;
g=NULL;
}
while (1);
return 0;
}
还有一类螺旋矩阵是从外往里的，如下图：
只要稍微改动就可以了，分析如下：
赋值的顺序和算法的原理不变，从大数开始赋值因此for循环改为：for(int i=size*size;i>=1;i--)，这时的结果为：
对称轴为x=a-x-1，带入即可。另外，这种矩阵不存在奇偶数不相同的问题。完整代码如下：
#include<iostream>
#include<time.h>
using namespace std;
void SpiralArray(int size, int** ar)
{
int a=size;
int y=a/2,x=a/2;//从中心点开始
for (int i=size*size;i>=1;i--)//(int i=1;i<=size*size;i++)
{
if (x<=a-y-1&&x>=y)
{
ar[y][a-x-1]=i;
x++;
}
else if (x>a-y-1&&x>y)
{
ar[y][a-x-1]=i;
y++;
}
else if (x>a-y-1&&x<=y)
{
ar[y][a-x-1]=i;
x--;
}
else if (x<=a-y-1&&x<y)
{
ar[y][a-x-1]=i;
y--;
}
}
}
int main()
{
int n;
do
{
cout<<"Please input a number(\"0\" is exit):";
cin>>n;
if (n==0)break;
int a=n;
int **g=new int *[a];
for (int i=0;i<a;i++)
g[i]=new int[a];
for (int p=0;p<a;p++)
for (int q=0;q<a;q++)
g[p][q]=0;
clock_t start,finish;
start = clock();
SpiralArray(n, g);
finish = clock();
double duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf( "%f seconds\n", duration );
char c;
cout<<"Output ?(y/n):";
cin>>c;
if ('n'==c)continue;
int ws=2;
if (n*n/100>=1)
ws=4;
else if (n*n/10>=1)
ws=3;
for (int y=0;y<a;y++)
{
for (int x=0;x<a;x++)
{
if (g[y][x]==0)
{
cout.width(ws);
cout<<' ';
}
else
{
cout.width(ws);
cout<<g[y][x];
}
}
cout<<endl;
}
for (i=0;i<a;i++)
{
delete[a] g[i];
g[i]=NULL;
}
delete[a] g;
g=NULL;
}
while (1);
return 0;
}