看见微软的图标我就想到了它~ 看见微软的图标我就想到了它

首先，我们来看两张图，不知道你有没有发现这个图和微软的图标好像啊~~~~

文章图片

文章图片

问题描述
有一个 NxN 整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。
要求：时间复杂度O(N2)，空间复杂度是O(N2)。
进阶：时间复杂度是O(N^2)，空间复杂度是O(1)
示例：

[[ [ 5, 1, 9,11],旋转90度后[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] ]]

分析问题
对于矩阵中的第一行元素来说，在经过90度旋转后，出现在了倒数第一列的位置上，如下图所示。

文章图片

并且，第一行的第 i 个元素在旋转后恰好是倒数第一列的第 i 个元素。对于第二行的元素也是如此，在旋转后变成倒数第二列的元素，并且第二行的第i个元素在旋转后恰好是倒数第二列的第i个元素。所以，我们可以得出规律，对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置，即对于矩阵中的 matrix[i] [j] 元素，在旋转后，它的新位置为 matrix [j] [n-i-1]。
所以，我们申请一个大小为 n * n 的新矩阵，来临时存储旋转后的结果。我们通过遍历matrix中的所有元素，根据上述规则将元素存放到新矩阵中的对应位置。在遍历完成后，再将新矩阵中复制到原矩阵即可。下面我们来看一下代码实现。

class Solution(object): def rotate(self, matrix): """ :type matrix: List[List[int]] :rtype: None Do not return anything, modify matrix in-place instead. """ #矩阵的大小 n = len(matrix) #申请一个辅助矩阵 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]#将辅助矩阵复制给矩阵 matrix[:] = temp

【看见微软的图标我就想到了它~】该算法的时间复杂度是O(N2)，空间复杂度O(N2)。
进阶
那我们如何在不使用辅助空间的情况下，实现矩阵的原地旋转呢？我们来看一下方法一中为什么要引入辅助空间，对于matrix中的元素，我们使用公式temp[j] [n - i - 1] = matrix[i] [j]进行旋转，如果不申请辅助矩阵，我们直接把元素 matrix[i] [j]，放到矩阵 matrix[j] [n - i - 1]位置，原矩阵中的matrix[j] [n - i - 1]元素就被覆盖了，这显然不是我们要的结果。

文章图片

文章图片

当知道了如何原地旋转矩阵之后，这里还有一点需要明确：我们应该选取哪些位置进行上述的原地交换操作呢？通过上面的分析可以知道，一次可以原地交换四个位置，所以：

当n为偶数时，我们需要选取 n^2 / 4 = (n/2) * (n/2)个元素进行原地交换操作，可以将该图形分为四块，可以保证不重复、不遗漏旋转所有元素；
当n为奇数时，由于中心的位置经过旋转后位置不变，我们需要选取 (n^2-1)/4=(n-1)/2 * (n+1) /2个元素进行原地交换操作，我们以5*5的矩阵为例，可以按照以下方式划分，进而保证不重复、不遗漏的旋转所有元素。

文章图片

下面我们来看一下代码的实现。

class Solution(object): def rotate(self, matrix): #矩阵的大小 n = len(matrix) for i in range(n // 2): for j in range((n + 1) // 2): #进行一轮原地旋转，旋转4个元素 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] = temp

该算法的时间复杂度是O(n^2)，空间复杂度是O(1)。