题目描述
本题要求将给定的 N 个正整数按非递增的顺序，填入“螺旋矩阵”。所谓“螺旋矩阵”，是指从左上角第 1 个格子开始，按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列，满足条件：m×n 等于 N；m≥n；且 m−n 取所有可能值中的最小值。
输入格式
输入在第 1 行中给出一个正整数 N，第 2 行给出 N 个待填充的正整数。所有数字不超过 104，相邻数字以空格分隔。
输出格式
输出螺旋矩阵。每行 n 个数字，共 m 行。相邻数字以 1 个空格分隔，行末不得有多余空格。
测试样例
Case 0:
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
Case 1:
5
3 2 4 1 5
5
4
3
2
1
Java代码
/**********************************************************************************
Submit Time Status Score Problem Compiler Run Time User
8/25/2019, 21:41:14 PA 24 1050 Java (openjdk) 177 ms wowpH
Case 7: TLE
**********************************************************************************/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String[] arr = br.readLine().split(" ");
int[] num = new int[N];
for (int i = 0; i < N; ++i) {
num[i] = Integer.parseInt(arr[i]);
}
Arrays.sort(num); // 所有数字升序排序
int n = (int) Math.sqrt(N); // 开方得到 n 的可能最大值
while (0 != N % n) { // 余数不为0，则 m 不是整数，不合要求
--n; // n 自减
}
int m = N / n; // m × n = N
int[][] matrix = new int[m][n]; // m × n 的矩阵
int direction = 0; // 方向，0代表向右，1代表向下，2代表向左，3代表向上
int k1 = 0, k2 = 0; // 矩阵下标
for (int i = N - 1; i >= 0; --i) { // 所有数
matrix[k1][k2] = num[i]; // 赋值给矩阵
switch (direction) { // 方向
case 0: // 向右
if (k2 + 1 < n && 0 == matrix[k1][k2 + 1]) {// 右边未越界且未赋值
++k2; // 向右移动
} else { // 右边越界或已经赋值
++k1; // 向下移动
direction = 1; // 改变方向为向下
}
break;
case 1: // 向下
if (k1 + 1 < m && 0 == matrix[k1 + 1][k2]) {// 下边未越界且未赋值
++k1; // 向下移动
} else { // 下边越界或已经赋值
--k2; // 向左移动
direction = 2; // 改变方向为向左
}
break;
case 2: // 向左
if (k2 - 1 >= 0 && 0 == matrix[k1][k2 - 1]) {// 左边未越界且未赋值
--k2; // 向左移动
} else { // 左边越界或已经赋值
--k1; // 向上移动
direction = 3; // 改变方向为向上
}
break;
default: // 向上
if (k1 - 1 >= 0 && 0 == matrix[k1 - 1][k2]) {// 上边未越界且未赋值
--k1; // 向上移动
} else { // 上边越界或已经赋值
++k2; // 向右移动
direction = 0; // 改变方向为向右
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n - 1; ++j) {
System.out.print(matrix[i][j] + " "); // 输出矩阵
}
System.out.println(matrix[i][n - 1]);
}
}
}