LeetCode 48 Rotate Image 解题思路和python代码
题目:
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Constraints:
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000
解题思路:
首先,转置这个matrix。
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
转置后变成:
[[1, 4, 7],
[2, 5, 8],
[3, 6, 9]]
接着,把 matrix 中的每一行都reverse。
[[7, 4, 1],
[8, 5, 2],
[9, 6, 3]]
完成将 matrix 旋转90°。
转置矩阵的 time complexity 是O(n^2),
reverse矩阵中每一行的 time complexity 也是 O(n^2)。
整体的 time complexity 是O(n^2)。
space complexity 是 O(1)。
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(n):
matrix[i].reverse()
return matrix
原文地址:https://blog.csdn.net/weixin_57266891/article/details/142754599
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!