This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Rotate the image

Given an n by n two-dimensional matrix matrix represents 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. Please do not use another matrix to rotate the image.

Example 1:

Input: matrix = [[1, 2, 3], [4 and 6], [7,8,9]] output: [,4,1 [7], [8,5,2], [9,6,3]]Copy the code

Example 2:

Input: matrix = [,1,9,11 [5],,4,8,10 [2], [13,3,6,7], [15,14,12,16]] output: [,13,2,5 [15], [14,3,4,1], [12,6,8,9], [16,7,10,11]]Copy the code

Example 3:

Input: matrix = [[1]] Output: [[1]Copy the code

Example 4:

Input: matrix = [1,2],[3,4]] output: [[3,1],[4,2]]Copy the code

Tip:

  • matrix.length == n
  • matrix[i].length == n
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

Thought analysis

The result of rotating the image 90 degrees clockwise can be obtained by combining the other two steps, first flipping the matrix horizontally and then the main diagonal. The time complexity of the solution is O (n2) {O (n ^ 2)} O (n2), space complexity is O (1) (1)} {O O (1).

The code shown

Solution a: time complexity is O (n2) {O (n ^ 2)} O (n2), space complexity is O (1) (1)} {O O (1).

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // flip horizontally
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp; }}// The main diagonal is inverted
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                inttemp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; }}}Copy the code

conclusion

Like this matrix rotation problem, of course, you can also find the rule, the corresponding expression after each node transformation, and then get the result, but it is also very important to master the common transformation of the matrix.