题目描述
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
样例
输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[[7,4,1],[8,5,2],[9,6,3]]
输入: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]]
算法1
思维题:
1、按右对角线翻转一次: 将右上角和左下角进行交换
2、按中轴翻转一次: 将前一半和后一半进行交换
时间复杂度:O(n^2)
空间复杂度:O(1)
C++ 代码
class Solution {
public:
/*
按右对角线翻转一次 按中轴翻转一次
1 2 3 1 4 7 7 4 1
4 5 6 2 5 8 8 5 2
7 8 9 3 6 9 9 6 3
1、按右对角线翻转一次:
将右上角和左下角进行交换
2、按中轴翻转一次:
将前一半和后一半进行交换
*/
void rotate(vector<vector<int>>& matrix) {
for(int i=0;i<matrix.size();i++)
{
for(int j=i;j<matrix[0].size();j++) // 右上角:因此j起始下标从i开始
{
swap(matrix[i][j],matrix[j][i]);
}
}
for(int i=0;i<matrix.size();i++)
{
for(int j=0,k=matrix[0].size()-1;j<k;j++,k--) // 每一行用两个指针分别从左、右同时走,直到j超过k,此处判断条件不能写j!=k
{
swap(matrix[i][k],matrix[i][j]);
}
}
}
};