大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天在脉脉看到一位同学秋招拿了腾讯、阿里、京东、美团四个offer，最终纠结是去京东还是美团。美团那边的业务比较核心但是给了白菜价，京东月薪比美团高了5k但是风评不太好。
大部分脉友还是倾向于选择京东，有多年职场经验的脉友认为选哪个以后都会后悔，直接选钱多的。还有些脉友疑惑为啥楼主不去鹅厂，有鹅选鹅不是已成为一种共识了么。还有些至今还没offer的同学催着楼主赶紧释放手里不要的offer，都排着队等着接呢。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「旋转图像」。
题目描述
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
举个例子：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
思路解析
这种题目没有什么好办法，只能由外到内一层一层的旋转。题目要求原地旋转，其实就是要求空间复杂度保证在 O(1)。
定义矩阵的边界left = top = 0，right = bottom = matrix.size() - 1。
旋转步骤如下：
先借助一个整型变量，旋转四个角的元素。 再借助同一个整型变量旋转基于四个角偏移的元素，最多偏移 right - left - 1。
把最外层全部旋转以后，缩小矩阵的边界， ++left、++top、--right、--bottom。如果left < right，进入步骤1，否则结束。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int left = 0, right = matrix.size() - 1;
while (left < right) {
for (int i = 0; i < right - left; ++i) {
//因为矩阵是正方形的
int top = left, bottom = right;
//保存做左上角的元素
int topleft = matrix[top][left + i];
//左下角旋转到左上角
matrix[top][left + i] = matrix[bottom - i][left];
//右下角旋转到左下角
matrix[bottom - i][left] = matrix[bottom][right - i];
//右上角旋转到右下角
matrix[bottom][right - i] = matrix[top + i][right];
//左上角旋转到右上角
matrix[top + i][right] = topleft;
}
++left;
--right;
}
}
};
python代码
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
left, right = 0, len(matrix) - 1
while left < right:
for i in range(right - left):
# 矩阵是正方形的
top, bottom = left, right
# 保存左上角的元素
topleft = matrix[top][left + i]
# 左下角旋转到左上角
matrix[top][left + i] = matrix[bottom - i][left]
# 右下角旋转到左下角
matrix[bottom - i][left] = matrix[bottom][right - i]
# 右上角旋转到右下角
matrix[bottom][right - i] = matrix[top + i][right]
# 左上角旋转到右上角
matrix[top + i][right] = topleft
left += 1
right -= 1
复杂度分析
时间复杂度： 需要遍历一遍矩阵matrix，所以时间复杂度是O(mn)，其中m是矩阵的行数，n是矩阵的列数。
空间复杂度： 只需要借助几个整型变量，故空间复杂度是O(1)。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
