【力扣算法】【python】旋转矩阵

【力扣算法】【python】旋转矩阵

题目链接题目描述题解思路

题目链接

https://leetcode-cn.com/problems/rotate-matrix-lcci/

题目描述

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例 #给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ], #原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ]

题解思路

从题意上解析，该题是需要将原二维数组的行转化为列，第一行的元素转化为最后一列，最后一行的元素转化为第一列，中间的行以此类推。

1，使用额外的内存空间 使用额外空间的情况比较容易考虑到，创建一个空的二维数组，然后从最后一行获取二维数组的元素，并将获取到的元素按顺序写入新创建的二维数组的第一列，之后的以此类推直到所有行都被处理完成。

class Solution(object): def rotate(self, matrix): """ :type matrix: List[List[int]] :rtype: None Do not return anything, modify matrix in-place instead. """ matrix_len = len(matrix) new_matrix = [[] for i in range(matrix_len)] for i in range(len(matrix)): row = matrix[matrix_len-1-i] for j in range(len(row)): new_matrix[j].append(row[j]) return new_matrix

2，不使用额外的空间 上面的使用额外空间的方法时间复杂度为O（n²），时间复杂度比较高。接下来可以稍微优化一下，同时也不需要使用额外的内存空间。 在矩阵的操作中，根据对角线翻转可以将原矩阵的行转化为列，这就初步达到我们的目的了。转化之后的矩阵的第一列是原矩阵的第一行，最后一列是原矩阵的最后一行。因此在对转化之后的矩阵的每一行进行倒序排列即可得到所需的结果。

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) # 使用对角线翻转将行转化为列 for i in range(n-1): for j in range(i+1, n): temp = matrix[i][j] matrix[i][j] = matrix[j][i] matrix[j][i] = temp # 使用切片的功能将每行的元素倒序排 for i in range(n): matrix[i] = matrix[i][::-1] return matrix 上面的算法执行效率还是不太高，后面继续改进