Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money

Rotate the array clockwise

Problem description

There is an NxN integer matrix, write an algorithm to rotate the matrix 90 degrees clockwise.

Requirements: Time complexity O(N^2), space complexity O(N^2).

Advanced: time complexity is O(N^2), space complexity is O(1)

Example:

[[[5, 1, 9, 11], rotate 90 degrees after [15, 13, 2, 5], [2, 4, 8, 10], = = = = = = = = = = = = > [14, 3, 4, 1], [13, 3, 6, 7], [12, 6, 8, 9]. [15,14,12,16] [16, 7,10,11]]Copy the code

To analyze problems

For the first row of elements in the matrix, after a 90-degree rotation, they appear in the position of the penultimate column, as shown in the figure below.

And the ith element in the first row happens to be the ith element in the penultimate column after the rotation. The same is true for the element in the second row, which becomes the element in the penultimate column after rotation, and the ith element in the second row happens to be the ith element in the penultimate column after rotation. Therefore, we can get the rule that for the JTH element in the ith row of the matrix, after rotation, it appears in the JTH position in the ith column to the last, that is, for the matrix[I] [j] element in the matrix, after rotation, its new position is matrix[j] [n-i-1].

So, we apply a new matrix of size n by n to temporarily store the rotated results. We iterate over all the elements in the matrix and store the elements in the corresponding positions in the new matrix according to the above rules. After traversal, copy the new matrix to the original matrix. Let’s take a look at the code implementation.

class Solution(object): def rotate(self, matrix): """ :type matrix: List[List[int]] :rtype: None Do not return anything, Temp = [[0] * n for _ in range(n)] temp = [[0] * n for _ in range(n)] For I in range(n): for j in range(n): temp[j][n-i-1] = matrix[I][j] # copy auxiliary matrix to matrix[:] = tempCopy the code

The time complexity of the algorithm is O(N^2), the space complexity is O(N^2).

The advanced

So how do we rotate the matrix in place without using the auxiliary space? For the elements in matrix, we use the formula **temp[j] [n-i-1] = matrix[I] [j]** for rotation. If we do not apply for auxiliary matrix, we directly apply the element matrix[I] [j], If the matrix[j] [n-i-1] is placed in the position of matrix **matrix[j] [n-i-1], the matrix[j] [n-i-1]** elements in the original matrix are covered, which is obviously not the result we want.

Now that we know how to rotate the matrix in place, there is one more thing to be clear about: which locations should we pick for the above in-place swap operation? According to the above analysis, four positions can be exchanged at one time, so:

  1. When n is even, we need to select n^ 2/4 = (n/2) * (n/2) elements for in-situ exchange operation, which can be divided into four blocks to ensure no repetition and rotation of all elements;
  2. When n is odd, since the position of the center remains unchanged after rotation, we need to select (n^2-1)/4=(n-1)/2 * (n+1) /2 elements for in-place exchange operation. Taking the 5*5 matrix as an example, it can be divided in the following way to ensure that all elements are rotated without repetition or omission.

Hiccup: I don’t know if you noticed how similar this image is to the Microsoft icon

Let’s look at the implementation of the code.

Class Solution(object): def rotate(self, matrix): def rotate(self, matrix): def rotate(self, matrix): for j in range((n + 1) // 2): # Take one turn in place, Temp = matrix[I][J] matrix[I][J] = matrix[n-j-1][I] matrix[n-j-1][I] = matrix[n-i-1][N-J-1] matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1] matrix[j][n - i - 1] = tempCopy the code

The time complexity of this algorithm is O(n^2) and the space complexity is O(1).