本题要求将给定的N个正整数按非递增的顺序,填入“螺旋矩阵”。所谓“螺旋矩阵”,是指从左上角第1个格子开始,按顺时针螺旋方向填充。要求矩阵的规模为m行n列,满足条件:m*n等于N;m>=n;且m-n取所有可能值中的最小值。
输入格式:
输入在第1行中给出一个正整数N,第2行给出N个待填充的正整数。所有数字不超过10,相邻数字以空格分隔。
输出格式:
输出螺旋矩阵。每行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
没有全对,有一个测试点错误,有两个测试点超时。
package com.hone.basical;
import java.util.Arrays;
import java.util.Scanner;
/**
* 原题目:https://www.patest.cn/contests/pat-b-practise/1049
* @author Xia
* 模拟旋转的方向,四个方向,先将一个个元素都装入到二维数组中
* 部分节点超时
*/
public class basicalLevel1049ArraySum { public static void main(String[] args) { Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[n];
for (int i = 0; i < a.length; i++) {
a[i] = in.nextInt();
}
//求出矩阵的m,n(使得对应的m-n最小)
int m = n;
int n2 = 1;
for (int i = (int) Math.sqrt(n)+1; i < a.length; i++) {
for (int j = (int) Math.sqrt(n); j > 0 ; j--) {
if (i*j==n) {
if ((i-j)<(m-n2)) {
m = i;
n2 = j;
}
break;
}
}
}
//先将数组排序
Arrays.sort(a); int[][] matrix = new int[m][n2]; //用一个二维数组来装填所有的数组
int i=0,j=0; //i表示行,j表示列
int index = n-1;
while (index>=0) {
//往右移动
for (; index>=0&&j<n2&&matrix[i][j]==0; j++) {
matrix[i][j]=a[index--];
}
i++;
j--; //考虑清楚这里面j--的原因?(因为在跳出循环之后j仍然做了一次加法)
//往下移动
for (; index>=0&&i<m&&matrix[i][j]==0; i++) {
matrix[i][j]=a[index--];
}
i--;
j--;
//往左边移动
for (; index>=0&&j>=0&&matrix[i][j]==0; j--) {
matrix[i][j]=a[index--];
}
i--;
j++;
//往上移动
for (; index>=0&&i>=0&&matrix[i][j]==0; i--) {
matrix[i][j]=a[index--];
}
i++;
j++;
}
for (int p = 0; p < m; p++) {
System.out.print(matrix[p][0]);
for (int q = 1; q < n2; q++) {
System.out.print(" " + matrix[p][q]);
}
System.out.println("");
} } }