This article originated from personal public account: TechFlow, original is not easy, for attention
Today, LeetCode 29, we’ll look at a simple matrix rotation problem.
The question
Given a two-dimensional square matrix, return the result after the matrix is rotated 90 degrees.
Let’s look at two examples:
Answer key
This GIF makes sense at first glance, which means we need to rotate a two-dimensional matrix 90 degrees clockwise. We all understand this question, but there is a limitation: we can’t apply additional arrays to help us, which limits our space usage.
It would be really easy if we didn’t have that constraint, we just figured out where each of these coordinates were rotated, and we just created a new array and filled it in.
Let’s ignore the specific data in the matrix and look at the coordinate changes before and after the rotation of the matrix. Here are the coordinates of the matrix before rotation:
After rotation, the coordinates become:
If we look at the two graphs above, we can see that for the coordinate (I, j), it should be (j, n-1-i) rotated by 90 degrees. N here is the number of rows.
Now that we have this, we can generalize. We find that the point at (I, j) rotates to (j, n-1-i). And (j, n – 1 – I) after the location of the point to the (n – 1 – I, n – 1 – j), in the same way (n – 1 – I, n – 1 – j) after rotation to the (n – 1 – j, I), finally, we found (n – 1 – j, I) after spinning back (I, j).
That is to say, for a rotation, (I, j), (j,n-1-i), (N-1-i, n-1-j), (n-1-j, I), the elements of the four positions swap positions, and do not affect the other positions. And this is actually pretty easy to figure out, because they’re giving you a square matrix.
Let’s take a look at the following figure to understand:
So what we do is we go through a quarter of the matrix, and then we take the four positions that are interchanged by coordinates, and then we swap their elements.
code
The code is really simple, just a few lines:
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"" "
Do not return anything, modify matrix in-place instead.
"" "
n = len(matrix)
Pay attention to the range and subscript
for i in range(n//2) :
for j in range(i, n- 1-i):
matrix[i][j], matrix[j][n- 1-i], matrix[n- 1-i][n- 1-j], matrix[n- 1-j][i] = \
matrix[n- 1-j][i], matrix[i][j], matrix[j][n- 1-i], matrix[n- 1-i][n- 1-j]
Copy the code