旋转图像/矩阵的重点是寻找旋转前后对应位置的坐标关系。
示例:
图1 旋转图像/矩阵的输入输出示意图
代码:
class Solution:
def rotate(self, matrix):
n = len(matrix)
for i in range(n // 2):
for j in range(i, n - 1 - i):
topleft = matrix[i][j]
matrix[i][j] = matrix[n - 1 - j][i]
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
matrix[j][n - 1 - i] = topleft
解释:
1)外层循环控制需要转的大圈圈数,内层循环控制每一圈需要转的小圈圈数,大小圈数的解释见图2,例如n=4,需要循环n // 2 = 2大圈,其中黄色循环箭头为第一大圈,绿色循环箭头为第二大圈。对于第一大圈,5->11->16->15->5为一小圈,同理1->10->12->13->1、9->7->14->2->9各为一小圈。
2)对于如何确定旋转前后位置坐标的对应关系,笔者是通过先确定再确定内层的方法,例如对于第一圈,固定i=0,然后观察大圈位置变化确定对应关系,接着改变i,观察内层圈数与i的对应关系进而修改对应坐标变化,如若先固定外层大圈循环,位置坐标变化应为:
matrix[0][j] = matrix[n - 1 - j][0]
matrix[n - 1 - j][0] = matrix[n - 1 - 0][n - 1 - j]
matrix[n - 1 - 0][n - 1 - j] = matrix[j][n - 1 - 0]
matrix[j][n - 1 - 0] = topleft
接着改变圈数,进入内层大圈循环,修改坐标变化:
matrix[i][j] = matrix[n - 1 - j][i]
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
matrix[j][n - 1 - i] = topleft
3)为了使算法空间复杂度为O(1),只需将每一次循环的左上角元素保存下来,接着采用逆向循环的顺序调整元素,最后将左上角元素归位即可,如此便无需重新开辟一个O() 空间来保存原始矩阵。
另外附上另一种实现方式:
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
l, r = 0, len(matrix) - 1
while l < r:
for i in range(r - l):
top, bot = l, r
topleft = matrix[top][l + i]
matrix[top][l + i] = matrix[bot - i][l]
matrix[bot - i][l] = matrix[bot][r - i]
matrix[bot][r - i] = matrix[top + i][r]
matrix[top + i][r] = topleft
l += 1
r -= 1