前言
从本文开始，我将开启一个新的系列文章的编写数据结构与算法，在本系列文章中，我将对牛客、LeetCode等主流算法刷题平台的精彩题目进行讲解，实现语言包括Python（主）、Javascript、C、C++，同时我也会将相关算法与我们的实际开发项目结合，帮助大家更好的理解这略显枯燥的算法。
【LeetCode】题目描述
给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例1：
给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ], 原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ]
示例 2：
给定 matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], 原地旋转输入矩阵，使其变为: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ]
思路提供
01 - 矩阵旋转示意图
观察转化前后的矩阵对应元素，不难发现：
图1.1 数字翻转示意图
图1.2 数字翻转示意图
图1.3 数字翻转示意图
图1.4 数字翻转示意图
02 - 总结思路
用arr代表二维数组 i、j 表示数组对应下标，替换过程为 :
- 记录当前元素 tmp=arr[0][0]
- 顺时针开始逐一替换
- arr[0][0]=arr[3][0]
- arr[3][0]=arr[3][3]
- arr[3][3]=arr[0][3]
- arr[0][3]=tmp
进而将这种情况推广到一般状态下即为 :
- tmp = arr[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] = temp
03 - 结论
观察变化前后的数组可知 , 先将数组的行进行翻转 , 然后再求翻转后矩阵的转置矩阵即可。
代码展示
- Python
class Solution: def rotate(self, matrix): """ :type matrix: List[List[int]] :rtype: void Do not return anything, modify matrix in-place instead. """ matrix.reverse() for i in range(len(matrix)): for j in range(i): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
- C++
class Solution { public: void rotate(vector<vector<int>>& matrix) { unsignedint n = matrix.size(); for(unsignedint i = 0; i < n/2; ++i){ for(unsignedint j = i; j < n - 1 - i; ++j){ int temp = 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] = temp; } } } };
本文总结
在本文中，我们通过简单的几个示意图讲解了如何对一个四阶矩阵进行原地（顺时针）旋转，并通过分析矩阵中的元素位置，将元素一般替换过程推广到普适的替换过程，最终得出本题的思路，我们最后还通过Python、C++对这个题目进行了实现，小伙伴们学会了吗？快去实现一下吧！
