一千题，No.0064（螺旋矩阵）

本文主要是介绍一千题，No.0064（螺旋矩阵），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本题要求将给定的 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

 解题思路：

按照题目硬求解，结果三个样例超时了

#include <bits/stdc++.h>using namespace std;int m,n;void func(int a)
{for(int i = sqrt(a)+1;i >= 1;--i){for(int j = i;j >= 1;--j){if(i * j == a){::m = i;::n = j;return;}}}
}int main()
{multiset<int,greater<int>> s;int a;cin >> a;if(a == 1){int num;cin >> num;cout << num;return 0;}else if(a == 0){return 0;}func(a);while(a--){int num;cin >> num;s.insert(num);}int arr[m][n];int check[m][n];memset(arr,0,sizeof(arr));memset(check,0,sizeof(check));pair<int,int> point = {0,0};auto t = s.begin();arr[0][0] = *t;check[0][0] = 1;++t;while(t != s.end()){while(point.second+1 < n && t != s.end() && check[point.first][point.second+1] == 0){arr[point.first][point.second+1] = *t;check[point.first][point.second+1] = 1;++point.second;++t;}while(point.first+1 < m && t != s.end() && check[point.first+1][point.second] == 0){arr[point.first+1][point.second] = *t;check[point.first+1][point.second] = 1;++point.first;++t;}while(point.second-1 >= 0 && t != s.end() && check[point.first][point.second-1] == 0){arr[point.first][point.second-1] = *t;check[point.first][point.second-1] = 1;--point.second;++t;}while(point.first-1 >= 0 && t != s.end() && check[point.first-1][point.second] == 0){arr[point.first-1][point.second] = *t;check[point.first-1][point.second] = 1;--point.first;++t;}}for(int i = 0;i < m;++i){for(int j = 0;j < n;++j){if(j != 0) cout << " ";cout << arr[i][j];}cout << endl;}return 0;
}

后来把set排序改为vector，sort排序依然超时，果断打开柳s的代码，发现不是排序的问题，是m,n的取值函数耗时太大

附上柳s的代码：

for (n = sqrt((double)a); n >= 1; n--){if (a % n == 0) {m = a / n;break;}}

c++代码如下：

#include <bits/stdc++.h>using namespace std;int main()
{vector<int> v;int a;cin >> a;int m,n;for (n = sqrt((double)a); n >= 1; n--){if (a % n == 0) {m = a / n;break;}}while(a--){int num;cin >> num;v.push_back(num);}sort(v.begin(),v.end(),greater<int>());int arr[m][n];int check[m][n];memset(arr,0,sizeof(arr));memset(check,0,sizeof(check));pair<int,int> point = {0,0};auto t = v.begin();arr[0][0] = *t;check[0][0] = 1;++t;while(t != v.end()){while(point.second+1 < n && t != v.end() && check[point.first][point.second+1] == 0){arr[point.first][point.second+1] = *t;check[point.first][point.second+1] = 1;++point.second;++t;}while(point.first+1 < m && t != v.end() && check[point.first+1][point.second] == 0){arr[point.first+1][point.second] = *t;check[point.first+1][point.second] = 1;++point.first;++t;}while(point.second-1 >= 0 && t != v.end() && check[point.first][point.second-1] == 0){arr[point.first][point.second-1] = *t;check[point.first][point.second-1] = 1;--point.second;++t;}while(point.first-1 >= 0 && t != v.end() && check[point.first-1][point.second] == 0){arr[point.first-1][point.second] = *t;check[point.first-1][point.second] = 1;--point.first;++t;}}for(int i = 0;i < m;++i){for(int j = 0;j < n;++j){if(j != 0) cout << " ";cout << arr[i][j];}cout << endl;}return 0;
}

这篇关于一千题，No.0064（螺旋矩阵）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---