Saltar al contenido

Rotar una matriz NxN en Java

Poseemos la mejor respuesta que encontramos online. Nosotros esperamos que te resulte de ayuda y si quieres comentarnos algún detalle que nos pueda ayudar a mejorar puedes hacerlo..

Visión general

Considere que una matriz de muestra podría verse así:

ABCD
EFGH
IJKL
MNOP

Para los propósitos de mi explicación, ABCD se considera como la fila 0, EFGH es la fila 1, y así sucesivamente. El primer píxel de la fila 0 es A.

Además, cuando hablo de la capa exterior, me refiero a:

ABCD
E  H
I  L
MNOP

Primero veamos el código que mueve los valores.

    int top = matrix[first][i]; // save top

La primera línea almacena en caché el valor en la posición superior. Esto se refiere a la posición en la fila superior de la matriz identificada por [first][i]. Por ejemplo: guardar el A.

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

La siguiente parte mueve el valor de la posición izquierda a la posición superior. Por ejemplo: tomando el M y ponerlo donde el A es.

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

La siguiente parte mueve el valor de la posición inferior a la posición izquierda. Por ejemplo: tomando el P y ponerlo donde el M es.

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

La siguiente parte mueve el valor de la posición derecha a la posición inferior. Por ejemplo: tomando el D y ponerlo donde el P es.

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

La última parte mueve el valor de la caché (cuál era la posición superior) a la posición correcta. Por ejemplo: poner el A desde el primer paso donde el D es.

A continuación, los bucles.

El bucle exterior va desde la fila 0 hasta la mitad del número total de filas. Esto se debe a que cuando gira la fila 0, también gira la última fila y cuando gira la fila 1, también gira la penúltima fila, y así sucesivamente.

El bucle interno se extiende desde la primera posición de píxel (o columna) en la fila hasta la última. Tenga en cuenta que para la fila 0, esto es desde el píxel 0 hasta el último píxel, pero para la fila 1, esto es desde el píxel 1 hasta el penúltimo píxel, ya que el primer y último píxel se rotan como parte de la fila 0 .

Entonces, la primera iteración del bucle externo hace que la capa externa gire. En otras palabras:

ABCD
EFGH
IJKL
MNOP

se convierte en:

MIEA
NFGB
OJKC
PLHD

Vea cómo la capa exterior ha girado en el sentido de las agujas del reloj, pero el núcleo interior no se ha movido.

Luego, la segunda iteración del bucle externo hace que la segunda fila gire (excluyendo el primer y último píxeles) y terminamos con:

MIEA
NJFB
OKGC
PLHD

Estoy escribiendo esta respuesta porque incluso después de leer la respuesta publicada por Jason arriba (es agradable y resolvió un par de preguntas que tenía) todavía no me quedaba claro qué papel juega la variable "compensación" en esta lógica, así que Pasando un par de horas para entender esto, pensé en compartirlo con todos.

Aquí se utilizan muchas variables y es importante comprender el significado de cada una.

Si miras la variable 'primero', es inútil, es esencialmente la 'capa' en sí, 'primero' no se modifica en absoluto en toda la lógica. Así que eliminé la 'primera' variable (y funciona, sigue leyendo).

Para comprender cómo cambia cada uno de estos valores en cada iteración del bucle for interno, imprimí los valores de estas variables. Eche un vistazo a la salida y comprenda qué valores cambian cuando nos movemos de una esquina a otra en el bucle for interno, qué valores permanecen constantes mientras atravesamos una sola capa y qué valores cambian solo cuando cambiamos la capa.

Una iteración del bucle interno mueve un solo bloque. La cantidad de iteraciones necesarias para mover una sola capa cambiará a medida que avancemos hacia adentro. La variable 'última' hace ese trabajo por nosotros, restringe el bucle interno (restringe la capa interna y evita que vayamos más allá del caparazón, basándose en la nomenclatura que usó Jason)

Es hora de estudiar el resultado.

He usado matriz de 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

Lo siento, pero no hay otra forma que reflexionar sobre cómo cambian los valores de layer, iy offset para comprender qué diablos está sucediendo aquí.

Finalmente el código

Aquí está el código donde eliminé lo innecesario primero y agregué todas las declaraciones de impresión, en caso de que alguien quiera jugar más. Este código también tiene inicialización e impresión de matriz aleatoria:

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

Acabo de ver que hay una forma más sencilla de escribir el código refactorizando "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
          
      
  

Comentarios y puntuaciones del post

Si para ti ha sido de ayuda nuestro post, nos gustaría que lo compartas con el resto entusiastas de la programación y nos ayudes a dar difusión a nuestra información.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)


Tags :

Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *