Rotation d'une matrice NxN en Java

J'écris cette réponse parce que même après avoir lu la réponse Postée par Jason ci-dessus (c'est bien et a résolu quelques questions que j'avais), il n'était toujours pas clair pour moi quel rôle est variable "offset" jouer dans cette logique, donc passer quelques heures à comprendre cela, j'ai pensé à le partager avec tout le monde.

Il y a beaucoup de variables utilisées ici et il est important de comprendre la signification de chacune.

Si vous regardez la variable 'first', c'est inutile, c'est essentiellement, la "couche" elle-même, "first" n'est pas modifiée du tout dans toute la logique. J'ai donc supprimé la variable' first ' (et cela fonctionne, lisez à l'avance).

Pour comprendre comment chacun de ces valeurs changent à chaque itération de la boucle intérieure que j'ai imprimé les valeurs de ces variables. Jetez un oeil à la sortie et comprenez quelles valeurs changent lorsque nous passons d'un coin à l'autre dans la boucle for interne, quelles valeurs restent constantes tout en traversant une seule couche et quelles valeurs changent seulement quand nous changeons la couche.

Une itération de boucle interne déplace un seul bloc. Nombre d'itérations nécessaires pour déplacer une seule couche va changer que nous allons vers l'intérieur. La variable 'last' fait ce travail pour nous, elle restreint la boucle interne (restreint la couche interne et nous empêche d'aller au-delà du shell, en s'appuyant sur la nomenclature utilisée par Jason)

Il est temps d'étudier la sortie .

J'ai utilisé la matrice 6x6.

Input: 

 315 301 755 542 955 33
 943 613 233 880 945 280
 908 609 504 61 849 551
 933 251 706 707 913 917
 479 785 634 97 851 745
 472 348 104 645 17 273

--------------Starting an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =0
buffer = 315
offset = i-layer = 0
Current Status: 

 472 301 755 542 955 315
 943 613 233 880 945 280
 908 609 504 61 849 551
 933 251 706 707 913 917
 479 785 634 97 851 745
 273 348 104 645 17 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =1
buffer = 301
offset = i-layer = 1
Current Status: 

 472 479 755 542 955 315
 943 613 233 880 945 301
 908 609 504 61 849 551
 933 251 706 707 913 917
 17 785 634 97 851 745
 273 348 104 645 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =2
buffer = 755
offset = i-layer = 2
Current Status: 

 472 479 933 542 955 315
 943 613 233 880 945 301
 908 609 504 61 849 755
 645 251 706 707 913 917
 17 785 634 97 851 745
 273 348 104 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =3
buffer = 542
offset = i-layer = 3
Current Status: 

 472 479 933 908 955 315
 943 613 233 880 945 301
 104 609 504 61 849 755
 645 251 706 707 913 542
 17 785 634 97 851 745
 273 348 917 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =0
last =5
i =4
buffer = 955
offset = i-layer = 4
Current Status: 

 472 479 933 908 943 315
 348 613 233 880 945 301
 104 609 504 61 849 755
 645 251 706 707 913 542
 17 785 634 97 851 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------
--------------Finished an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of inner for loop------------------
layer =1
last =4
i =1
buffer = 613
offset = i-layer = 0
Current Status: 

 472 479 933 908 943 315
 348 785 233 880 613 301
 104 609 504 61 849 755
 645 251 706 707 913 542
 17 851 634 97 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =1
last =4
i =2
buffer = 233
offset = i-layer = 1
Current Status: 

 472 479 933 908 943 315
 348 785 251 880 613 301
 104 609 504 61 233 755
 645 97 706 707 913 542
 17 851 634 849 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------

--------------Starting an iteration of inner for loop------------------
layer =1
last =4
i =3
buffer = 880
offset = i-layer = 2
Current Status: 

 472 479 933 908 943 315
 348 785 251 609 613 301
 104 634 504 61 233 755
 645 97 706 707 880 542
 17 851 913 849 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------
--------------Finished an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of OUTER FOR LOOP------------------

--------------Starting an iteration of inner for loop------------------
layer =2
last =3
i =2
buffer = 504
offset = i-layer = 0
Current Status: 

 472 479 933 908 943 315
 348 785 251 609 613 301
 104 634 706 504 233 755
 645 97 707 61 880 542
 17 851 913 849 945 955
 273 745 917 551 280 33
--------------Finished an iteration of inner for loop------------------
--------------Finished an iteration of OUTER FOR LOOP------------------

 472 479 933 908 943 315
 348 785 251 609 613 301
 104 634 706 504 233 755
 645 97 707 61 880 542
 17 851 913 849 945 955
 273 745 917 551 280 33

Désolé mais il n'y a pas d'autre moyen que de réfléchissez à la façon dont les valeurs de la couche, i et offset changent pour comprendre ce qui se passe ici.

Enfin, le code

Voici le code où j'ai supprimé inutile en premier et ajouté toutes les instructions d'impression, au cas où quelqu'un voudrait jouer plus. Ce code a également une initialisation et une impression de matrice aléatoires:

package com.crackingthecodinginterview.assignments.chap1;

public class Problem6RotateMatrix90 {

    public static void main(String args[]){
        int[][] matrix = new int[6][6];
        initializeMatrix(matrix,6);
        System.out.println("Input: ");
        printMatrix(matrix,6);
        rotate(matrix,6);
        printMatrix(matrix,6);
    }

    public static void rotate(int[][] matrix, int n) {
        for (int layer = 0; layer < n / 2; ++layer) {
            System.out.println("\n--------------Starting an iteration of OUTER FOR LOOP------------------");

            int last = n - 1 - layer;
            for(int i = layer; i < last; ++i) {
                int offset = i - layer;
                int buffer = matrix[layer][i]; // save top
                System.out.println("\n--------------Starting an iteration of inner for loop------------------");
                System.out.println("layer ="+layer);

                System.out.println("last ="+last);
                System.out.println("i ="+i);

                System.out.println("buffer = "+buffer);
                System.out.println("offset = i-layer = "+ offset);

                // left -> top
                matrix[layer][i] = matrix[last-offset][layer];          

                // bottom -> left
                matrix[last-offset][layer] = matrix[last][last - offset]; 

                // right -> bottom
                matrix[last][last - offset] = matrix[i][last]; 

                // top -> right
                matrix[i][last] = buffer; // right <- saved top

                //print
                System.out.println("Current Status: ");
                printMatrix(matrix,6);
                System.out.println("--------------Finished an iteration of inner for loop------------------");
            }
            System.out.println("--------------Finished an iteration of OUTER FOR LOOP------------------");

        }
    }

    public static void printMatrix(int[][] matrix,int n){
        System.out.print("\n");
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                System.out.print(" "+matrix[i][j]);
            }
            System.out.print("\n");
        }
    }

    public static void initializeMatrix(int[][] matrix,int n){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                matrix[i][j]=(int) (Math.random() * 1000);
            }
        }
    }

}

Juste vu qu'il existe un moyen plus simple d'écrire le code en refactorisant "Last-offset":

  public static void rotateInPlace90DegreesClockwise(int[][] matrix) {
      int n = matrix.length;
      int half = n / 2;

      for (int layer = 0; layer < half; layer++) {
          int first = layer;
          int last = n - 1 - layer;

          for (int i = first; i < last; i++) {
              int offset = i - first;
              int j = last - offset;
              int top = matrix[first][i]; // save top

              // left -> top
              matrix[first][i] = matrix[j][first];          

              // bottom -> left
              matrix[j][first] = matrix[last][j]; 

              // right -> bottom
              matrix[last][j] = matrix[i][last]; 

              // top -> right
              matrix[i][last] = top; // right <- saved top
          }
      }
  }

Vérifiez cette solution pour le faire en place.

public void rotateMatrix(Pixel[][] matrix) {

    for (int i = 0; i < matrix.length / 2; i++) {

        for (int j = 0; j < matrix.length - 1 - 2 * i; j++) {
            Pixel tmp = matrix[j + i][matrix.length - 1 - i];
            matrix[j + i][matrix.length - 1 - i] = matrix[i][j + i];
            matrix[i][j + i] = matrix[matrix.length - 1 - j - i][i];
            matrix[matrix.length - 1 - j - i][i] = matrix[matrix.length - 1 - i][matrix.length - 1 - j - i];
            matrix[matrix.length - 1 - i][matrix.length - 1 - j - i] = tmp;
        }
    }
}

La solution Simple est:

int[][] a = { {00,01,02  }, { 10,11,12} ,{20,21,22}};
System.out.println(" lenght " + a.length);

int l = a.length;

for (int i = 0; i <l; i++) {

    for (int j = l - 1; j >= 0; j--) {
        System.out.println(a[j][i]);
    }
}

  /**
 * @param args
 */
public static void main(String[] args) {
    int n = 5; //5x5 matrix
    int[][] matrixInitial = initMatrix(n);
    int[][] matrixFinal = rotate(matrixInitial, n);
    System.out.println(matrixFinal.length);

    int m = 4; //4x4 matrix
    int[][] matrixInitial2 = initMatrix(m);
    int[][] matrixFinal2 = rotate(matrixInitial2, m);
    System.out.println(matrixFinal2.length);
}

private static int[][] rotate(int[][] matrixInitial, int n) {
//it is much like square layers. each layer will be read and rotated
    int layerCount = (n + 1) / 2; 
    System.out.println("n: " + n + " layerCount: " + layerCount);
    int[][] matrixFinal = new int[n][n];
    if (n % 2 == 1) { // for odd # layers the centre does not move
        matrixFinal[n / 2][n / 2] = matrixInitial[n / 2][n / 2];
        layerCount -= 1;
    }

    for (int i = 0; i < layerCount; i++) {
        int width = n - (2 * i); // width of the layer
        System.out.println("width: " + width);
        int[] top = new int[width]; // read top
        for (int j = 0; j < width; j++) {
            top[j] = matrixInitial[i][i + j];
        }
        System.out.println("top: " + Arrays.toString(top));

        //OK TOP TO RIGHT

        for (int j = 0; j < width; j++) { // move top to right 
            matrixFinal[j+i][width-1+i] = top[j];
        }

        int[] tempLeft = new int[width]; // left will be read backwards
        for (int j = 0; j < width; j++) { // reverse the temp
            tempLeft[j] = matrixInitial[i + j][i];
        }

        int[] left = new int[width];
        int indexTemp = 0;
        for (int j = width-1; j >= 0; j--) { // move temp to left
            left[indexTemp++] = tempLeft[j];
        }
        System.out.println("left: " + Arrays.toString(left));

        //OK LEFT TO TOP

        for (int j = 0; j < width; j++) { // move left to top
            matrixFinal[i][j + i] = left[j];
        }

        int[] bottom = new int[width]; read bottom
        for (int j = 0; j < width; j++) {
            bottom[j] = matrixInitial[width - 1 + i][j + i];
        }
        System.out.println("bottom: " + Arrays.toString(bottom));

        //OK BOTTOM TO LEFT

        for (int j = 0; j < width; j++) { // move bottom to left
            matrixFinal[j+i][i] = bottom[j];
        }

        int[] tempRight = new int[width]; // right will be read backwards
        for (int j = 0; j < width; j++) {
            tempRight[j] = matrixInitial[j + i][width - 1 + i];
        }
        int[] right = new int[width]; //reverse the temp
        int indexTemp2 = 0;
        for (int j = width; j > 0; j--) {
            right[indexTemp2++] = tempRight[j - 1];
        }
        System.out.println("right: " + Arrays.toString(right));

        //OK RIGHT TO BOTTOM
        for (int j = 0; j < width; j++) { // move right to bottom
            matrixFinal[width-1+i][j + i] = right[j];
        }

    }
    for (int i = 0; i < n; i++) {
        System.out.println(Arrays.toString(matrixFinal[i]));
    }
    return matrixFinal;
}

private static int[][] initMatrix(int n) { // init the matrix
    int[][] matrix = new int[n][n];
    int fill = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            matrix[i][j] = fill++;
        }
    }

    for (int i = 0; i < n; i++) {
        System.out.println(Arrays.toString(matrix[i]));
    }
    System.out.println("******");
    return matrix;
}

Voici ma solution en JavaScript, elle échange des valeurs entre une ligne et une colonne à partir du bord supérieur droit, allant vers l'intérieur jusqu'à ce que la paire inférieure à gauche soit échangée.

function rotateMatrix(arr) {
    var n = arr.length - 1;

    for (var i = 0; i < n; i++) {
        for (var j = 0; j < n - i; j++) {
            var temp = arr[i][j];

            arr[i][j] = arr[n - j][n - i]; // top row
            arr[n - j][n - i] = temp; // right column
        }
    }

    return arr;
}

Voici une solution simple qui fonctionne parfaitement pour moi.

 private int[][] rotateMatrix(int[][] matrix)
    {
        for(int i=0;i<matrix.length-1;i++)
        {
            for(int j =i;j<matrix[0].length;j++)
            {
                if(i!=j) {
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = temp;
                }
            }
        }
        return matrix;
    }