This is the 15th day of my participation in the August More Text Challenge. For details, see:August is more challenging

preface

The rotation image of problem 48 is as follows:

Given an N by n two-dimensional matrix matrix representing an image. Please rotate the image 90 degrees clockwise.

You have to rotate the image in place, which means you need to modify the input two-dimensional matrix directly. Do not use another matrix to rotate the image.

Example 1:

Example 2:

A, thinking

The hardest part of this problem is that you need to rotate the image in place, which means you can only use a constant amount of extra space to achieve the transformation.

The realization idea is mainly divided into the following two parts:

  • Divide the circle conversion, from the outside to the inside, such as:4 x 4The matrix of PI, there are two circles
  • When you do a loop, you just focus on the frontn- 1 - iAnd each element needs to be swapped three times

Graphic rotation in place

With matrix = [,1,9,11 [5], [2,4,8,10], [13,3,6,7], [15,14,12,16]] as an example

Divide the circle conversion, from the outside to the inside

This 4 x 4 matrix goes to the right two cycles, and we just have to deal with those two cycles

I’m going to switch around

The outer ring ① is taken as an example here

All we need to do is focus on 5, 1, 9

The exchange logic is as follows (using only the first element as an example) :

  1. exchangematrix[0][0] 和 matrix[0][3]

  1. exchangematrix[0][0] 和 matrix[3][3]

  1. exchangematrix[0][0] 和 matrix[3][0]

Law of exchange

The rules of exchange I have made the following summary:

  1. In front of the circlen - 1- iAs a benchmark
  2. A certain point needs to be exchanged three times. The characteristics of the three points are as follows:
    • The first point of exchange: column fixation
    • The second point of exchange: row fixation
    • The third point of exchange: column fixation

Second, the implementation

The implementation code

The implementation code is consistent with the idea

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // rotation n-2 times (n>2)
        for (int i=0; i == 0 || i<n-2; i++) {
            int end = n- 1 - i;
            // How many points do I have to replace for each turn? N minus 2 times I minus 1
            for (int j=0; j<n-2*i-1; j++) {
                // Each point value needs to be replaced three times
                for (int m=0; m<3; m++) {
                    int temp = matrix[i][i+j];
                    if (m==0) { // Replace the first number (column fixed)
                        matrix[i][i+j] = matrix[i + j][end];
                        matrix[i + j][end] = temp;
                    } else if (m==1) {// Replace the second number (row fixed)
                        matrix[i][i+j] = matrix[end][end - j];
                        matrix[end][end - j] = temp;
                    } else {    // Replace the third number (column fixed)
                        matrix[i][i+j] = matrix[end - j][i];
                        matrix[end - j][i] = temp;
                    }
                }
            }
        }
    }
Copy the code

The test code

public static void main(String[] args) {
    int[][] matrix = {{5.1.9.11}, {2.4.8.10}, {13.3.6.7}, {15.14.12.16}};
    int[][] matrix1 = {{1.2}, {3.4}};
    new Number48().rotate(matrix1);
}
Copy the code

The results of

Third, summary

Thank you for seeing the end, it is my great honor to help you ~♥