PAT——1050. 螺旋矩阵

本题要求将给定的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("");
        }
        
     }

}