在 java 中生成螺旋矩阵的算法

algorithm to generate a spiral matrix in java

Write a class that, given a positive integer N, creates and returns a square matrix NxN made out of integers that displays the numbers from 1 to n^2 in a spiral

在我的class中有四种方法,其中三种是方向,而spiral()方法应该把每个数字都放在正确的位置

public static int[][] spiral(int n) {
    int[][] res;
    int i,j;
    int num;
    int direction;

    /** variables initializzazion */
    res=new int[n][n];
    i=0;
    j=0;
    res[i][j]=1;
    direction=0;


    for(num=2; num<=n*n; num++) {
        direction = updateDirection(direction, i, j, n);
        if ((direction==1) || (direction==3))
            i=updateRow(i, direction);
        else
            j=updateColoumn(j, direction);
        res[i][j]=num;
    }
    return res;
}

遗憾的是,当我尝试 运行 时,我得到一个 ArrayIndexOutOfBoundException,这似乎是由 res[i][j]=1;.

引起的

我怎样才能修复它,使数组仍然从 1 开始并上升到 N*N?

编辑:添加了updateDirection()方法

要更好地理解此方法,请查看此图片:

public static int updateDirection(int direction, int i, int j, int n) {

    /** if on the secondary diagonal direction is 1 or 3 */
    if(i+j==n-1)
        direction++;
    /** if on the lower half of the main diagonal, direction is 2 */
    if(i==j && j+j>=n)
        direction++;
    /** if on the row below the higher half of the main diagonal, direction is 0 */
    if(i==j+1 && i+j<n)
        direction++;
    /** in other cases, direction doesn't change */

    return direction%4;
    }

Edit2:这是我的测试方法:

public static void testSpiral(){
    for(int n=0; n<=5; n++)
        System.out.println(Arrays.deepToString(spiral(n)));
}

Edit3:添加了 updateRow()updateColoumn() 方法:

public static int updateRow(int i, int direction) {
    int res;
    if(direction==1)
        res=i+1; //moves from top to bottom
    else
        res = i-1; //moves from bottom to top
    return res;
}

public static int updateColoumn(int j, int direction){
    int res;
    if(direction==0)
        res=j+1; //moves from left to right
    else
        res=j-1; //moves from right to left
    return res;

这可能会或可能不会如您所愿。我认为弄清楚它的作用可能会教给你很多东西。

import java.util.Arrays;

public class Spiral {

        static final int TEST_X = 5;
        static final int TEST_Y = 5; 
        static enum Direction {UP, DOWN, LEFT, RIGHT};

        public static void main( String ... args ){
            for( int i = TEST_X - 1; i > 0; i--) { 
                for ( int j = TEST_Y - 1 ; j > 0; j-- ){
                    int arr[][] = spiral(i,j);

                    for( int[] inner : Arrays.asList(arr))
                        System.out.println(Arrays.toString(inner));

                    System.out.println("############\n");
                }
            }
        }

        public static int[][] spiral( int rows, int cols ) { 
            if( cols <= 0 || rows <= 0 ){
                throw new IllegalArgumentException("Spiral requires dimensions greater than 0.");
            }
            int arr[][] = new int[rows][cols];

            int     count             = 1; 
            int     cur_col             = -1; 
            int     cur_row             = 0;
            int     consecutive_turns = 0;
            Direction dir             = Direction.RIGHT;


            while( true ) {

                if( consecutive_turns == 4)
                       return arr;

                switch( dir ){
                case RIGHT : 

                    if( cur_col + 1 == cols || arr[cur_row][cur_col + 1] > 0){ 

                        dir = Direction.DOWN;
                        consecutive_turns++;

                    } else {
                        consecutive_turns = 0;
                        cur_col++;
                        arr[cur_row][cur_col] = count;
                        count++;
                    }
                    break;

                case LEFT :

                    if( cur_col - 1 < 0 || arr[cur_row][cur_col - 1] > 0 ){
                        dir = Direction.UP;
                        consecutive_turns++;
                    } else {
                        consecutive_turns = 0;
                        cur_col--;
                        arr[cur_row][cur_col] = count;
                        count++;
                    }
                    break; 

                case UP : 

                    if( cur_row - 1 < 0 || arr[cur_row - 1][cur_col] > 0 ){
                        dir = Direction.RIGHT;
                        consecutive_turns++;
                    } else {
                        consecutive_turns = 0;
                        cur_row--;
                        arr[cur_row][cur_col] = count;
                        count++;
                    }
                    break; 

                case DOWN : 

                    if( cur_row + 1 == rows || arr[cur_row + 1][cur_col] > 0 ){
                        dir = Direction.LEFT;
                        consecutive_turns++;
                    } else {
                        consecutive_turns = 0;
                        cur_row++;
                        arr[cur_row][cur_col] = count;
                        count++;
                    }
                    break;

                default : 
                    System.err.println("The end has come!");
                    System.exit(1); 

                }
            }
        }
    }

testSpiral 方法中,您在 0 中启动 for 循环,因此创建的数组 res 大小为 0

当您尝试设置 res[i][j] = 1 时,您正在尝试访问数组中的第一个元素,但是 none.

只需在 i=1 中启动 for:

public static void testSpiral(){
    for(int n=1; n<=5; n++)
        System.out.println(Arrays.deepToString(spiral(n)));
}

您不需要class。此函数returns 顺时针旋转矩阵。希望能帮到你。

int[][] spiralNumbers(int n) {
    int[][] matrix = new int[n][n];
    for (int step = 0, a = 0, size; step < n/2; step++) {
        size = (n - step * 2 - 1);
        for (int i = 0, chunk, chunkIndex, chunkOffset; i < 4 * size; i++) {
            chunk = i / size;
            chunkIndex = i % size;
            chunkOffset = n - step - 1;
            switch (chunk) {
                case 0:
                    matrix[step][chunkIndex + step] = a+1;
                    break;
                case 1:
                    matrix[chunkIndex + step][chunkOffset] = a+1;
                    break;
                case 2:
                    matrix[chunkOffset][chunkOffset - chunkIndex] = a+1;
                    break;
                case 3:
                    matrix[chunkOffset - chunkIndex][step] = a+1;
                    break;
                default:
                    throw new IndexOutOfBoundsException();
            }
            a++;
        }
        if (n % 2 == 1) {
            matrix[n/2][n/2] = n * n;
        }
    }
    return matrix;
}