How to rotate an array in Java?

Question

How to rotate an array in Java?

Navigation

#1 by (4 votes)

2

I have a two-dimensional array, size M x N, that stores tiles of a map, in the following format:

[1, 2, 3],

[4, 5, 6],

[7, 8, 9],

[10, 11, 12]

And I want to rotate in 90º (ie rotate the map so that the North is in the East). The rotated example looks like this:

[10, 7, 4, 1],

[11, 8, 5, 2],

[12, 9, 6, 3]

Note that the array has changed size: it has been for N x M after the rotation. This is similar to what happens when you rotate certain pieces of the Tetris game: the longer (high) it is, the wider it will be when it is rotated.

How do you rotate this type of two-dimensional array in Java?

java array array-multidimensional

asked by anonymous 08.03.2017 / 05:48

1 answer

Database CodeFirst Entity Framework, 1-0..1, 1-N Notification remains in the status bar even after the click

score 4 · Accepted Answer

In the example, the 4x3 array can be declared as follows:

 int[][] a1 = new int[][]{   new int[]{1,2,3},
                             new int[]{4,5,6},
                             new int[]{7,8,9},
                             new int[]{10,11,12}};

In other words, it is an array of int arrays. Below are the codes for rotating two-dimensional arrays clockwise and counterclockwise, respectively:

public static int[][] rotacionarMatrizHorario(int[][] matriz) {
    int largura = matriz.length;
    int altura = matriz[0].length;
    int[][] ret = new int[altura][largura];
    for (int i=0; i<altura; i++) {
        for (int j=0; j<largura; j++) {
            ret[i][j] = matriz[largura - j - 1][i];
        }
     }
    return ret;
}


public static int[][] rotacionarMatrizAntiHorario(int[][] matriz) {
    int largura = matriz.length;
    int altura = matriz[0].length;   
    int[][] ret = new int[altura][largura];
    for (int i=0; i<altura; i++) {
        for (int j=0; j<largura; j++) {
            ret[i][j] = matriz[j][altura - i - 1];
        }
    }
    return ret;
}

To turn a matrix "upside down", simply rotate it twice by 90 °, thus totaling 180 °:

[12, 11, 10],
[9, 8, 7],
[6, 5, 4],
[3, 2, 1]

When you rotate the original matrix 90 degrees three times, that is, 270 degrees, the result is the same as rotating the matrix 90 degrees counterclockwise. The result will be this:

[3, 6, 9, 12],
[2, 5, 8, 11],
[1, 4, 7, 10]

This is the simplest implementation: the methods have a complexity of the order of O (N²), where N is the size of the matrix, or more precisely O (M * N), where M is the height and N is the width of the matrix.

Depending on the application, more efficient ways to rotate the array can be implemented. It is possible to reduce the complexity for O (N) * log (N), or even more if special treatments are considered in the case of sparse matrices, or even optimizations according to the architecture of the computer that will perform the rotations.