题目
给定一个 n × n 的二维矩阵,将其顺时针旋转90度
例子
rotateMatrix([[1,2,3],[4,5,6],[7,8,9]]) -> [[7,4,1],[8,5,2],[9,6,3]]
假设
- 输入的参数不为空
tips
- 你能想到不使用额外二维数组的方法吗?
答案
解法1
def rotateMatrix(matrix):
n = len(matrix)
# 水平翻转
for i in range(n // 2):
for j in range(n):
matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
# 主对角线翻转
for i in range(n):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
return matrix
性能:
- 时间复杂度
O(n^2)
- 空间复杂度
O(1)
关键点:
- 翻转两次
解法2:
def rotateMatrix(matrix: list) -> list:
n = len(matrix)
newmatric = [[0 for i in range(n)] for j in range(n)]
print(newmatric)
for i in range(n):
for j in range(n):
newmatric[i][j] = matrix[n-1-j][i]
return newmatric