本题要求将给定的 N 个正整数按非递增的顺序，填入“螺旋矩阵”。所谓“螺旋矩阵”，是指从左上角第 1 个格子开始，按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列，满足条件：m×n 等于 N；m≥n；且 m−n 取所有可能值中的最小值。
输入格式：
输入在第 1 行中给出一个正整数 N，第 2 行给出 N 个待填充的正整数。所有数字不超过 104，相邻数字以空格分隔。
输出格式：
输出螺旋矩阵。每行 n 个数字，共 m 行。相邻数字以 1 个空格分隔，行末不得有多余空格。
输入样例：
12
37 76 20 98 76 42 53 95 60 81 58 93
输出样例：
98 95 93
42 37 81
53 20 76
58 60 76问题总结：
1.没什么特别的，就是一个找规律的题，和机器人的那一道题有些类似：机器人控制。但是需要解决几个问题。
2.寻找 m * n = N 的两个数，且有 m>n & min(m-n) 比较笨的方法。
void get_m_n(int N, int &m,int &n)
{
int min = N ;
for(int i = 1; i <= N; i++)
{
for (int j = i; j <= N; j++)
{
if(i*j == N)
{
if(min > (j-i))
{
min = (j-i);
m = j;
n = i;
}
}
if(i*j > N)
{
break;
}
}
}
}3.简单的选择排序
void sort(int *nums,int size)
{
int t;
for(int i=0;i<size;i++)
{
for(int j = i+1; j<size; j++)
{
if(nums[i]<nums[j])
{
t = nums[i];
nums[i] = nums[j];
nums[j] =t;
}
}
}
}4.数据范围，m和n的取值决定了程序能不能通过测试点，因此二维数组不能开太大，当然可以用一维数组来优化。开辟 m * n ＝N的一维数组，将二维矩阵按行顺序存储，通过计算还原元素在二维数组位置的下标，即：一维元素 index = i * n + j；i和j代表二维中的下标，n代表列col数量。
优化前的内存
优化后的内存
5.总体实现：未优化
#include <iostream>
#include<cstring>
using namespace std;
void get_m_n(int N, int &m,int &n)
{
int min = N ;
for(int i = 1; i <= N; i++)
{
for (int j = i; j <= N; j++)
{
if(i*j == N)
{
if(min > (j-i))
{
min = (j-i);
m = j;
n = i;
}
}
if(i*j > N)
{
break;
}
}
}
}
void sort(int *nums,int size)
{
int t;
for(int i=0;i<size;i++)
{
for(int j = i+1; j<size; j++)
{
if(nums[i]<nums[j])
{
t = nums[i];
nums[i] = nums[j];
nums[j] =t;
}
}
}
}
int main(int argc, char const *argv[])
{
bool r = true,d = false,l = false,u=false;
int N;
cin>>N;
int *nums = new int[N];
memset(nums, 0, sizeof(int)*N);
for(int i = 0; i <N; i++)
{
cin>>nums[i];
}
sort(nums,N);
int m=0,n=0;
get_m_n(N,m,n);
int ans[10000][100] = {0};
int i=0,j=-1;
int heng = n,shu = m -1;
for(int index = 0; index < N; )
{
if(r)
{
for(int step = 0; step < heng; step++)
{
ans[i][++j] = nums[index++];
r = false;
l = false;
u = false;
d = true;
}
heng--;
}
if(d)
{
for(int step=0; step < shu;step++)
{
ans[++i][j] = nums[index++];
d = false;
u = false;
r = false;
l = true;
}
shu--;
}
if(l)
{
for(int step = 0; step < heng; step++)
{
ans[i][--j] = nums[index++];
l = false;
r = false;
d = false;
u = true;
}
heng--;
}
if(u)
{
for(int step=0; step < shu; step++)
{
ans[--i][j] = nums[index++];
u = false;
l = false;
d = false;
r = true;
}
shu--;
}
}
for(int row = 0; row < m; row++)
{
for (int col = 0; col < n; col++)
{
if(col<n-1)
{
cout<<ans[row][col]<<" ";
}
else
{
cout<<ans[row][col];
}
}
cout<<endl;
}
return 0;
}
6.优化方案
#include <iostream>
#include<cstring>
using namespace std;
void get_m_n(int N, int &m,int &n)
{
int min = N ;
for(int i = 1; i <= N; i++)
{
for (int j = i; j <= N; j++)
{
if(i*j == N)
{
if(min > (j-i))
{
min = (j-i);
m = j;
n = i;
}
}
if(i*j > N)
{
break;
}
}
}
}
void sort(int *nums,int size)
{
int t;
for(int i=0;i<size;i++)
{
for(int j = i+1; j<size; j++)
{
if(nums[i]<nums[j])
{
t = nums[i];
nums[i] = nums[j];
nums[j] =t;
}
}
}
}
int convert_i_j(int i, int j, int n)
{
return i*n+j;
}
int main(int argc, char const *argv[])
{
bool r = true,d = false,l = false,u=false;
int N;
cin>>N;
int *nums = new int[N];
memset(nums, 0, sizeof(int)*N);
for(int i = 0; i <N; i++)
{
cin>>nums[i];
}
sort(nums,N);
int m=0,n=0;
get_m_n(N,m,n);
int *answer= new int[m*n];
int i=0,j=-1;
int heng = n,shu = m -1;
for(int index = 0; index < N; )
{
if(r)
{
for(int step = 0; step < heng; step++)
{
j++;
int value = nums[index++];
int index_m_n = convert_i_j(i,j,n);
answer[index_m_n] = value;
r = false;
l = false;
u = false;
d = true;
}
heng--;
}
if(d)
{
for(int step=0; step < shu;step++)
{
i++;
int value = nums[index++];
int index_m_n = convert_i_j(i,j,n);
answer[index_m_n] = value;
d = false;
u = false;
r = false;
l = true;
}
shu--;
}
if(l)
{
for(int step = 0; step < heng; step++)
{
j--;
int value = nums[index++];
int index_m_n = convert_i_j(i,j,n);
answer[index_m_n] = value;
l = false;
r = false;
d = false;
u = true;
}
heng--;
}
if(u)
{
for(int step=0; step < shu; step++)
{
i--;
int value = nums[index++];
int index_m_n = convert_i_j(i,j,n);
answer[index_m_n] = value;
u = false;
l = false;
d = false;
r = true;
}
shu--;
}
}
for(int row = 0; row < m; row++)
{
for (int col = 0; col < n; col++)
{
if(col<n-1)
{
cout<<answer[row*n+col]<<" ";
}
else
{
cout<<answer[row*n+col];
}
}
cout<<endl;
}
return 0;
}
