题解 | #【冲刺双百】顺时针旋转矩阵#

时间复杂度为O(1)的思路

1. 想要控制时间复杂度在O(1)则需要在原矩阵上操作
2. 寻找规律：分析顺时针旋转后位置的变化，得到：

mat[i][j]->m[j][n-1-i]
构造出坐标转移方程：f(i,j)=(j,n-1-i)
设f_next0=(i,j) 继续推导：

• f_next1=f(i,j)=(j,n-1-i)
  
• f_next2=f(j,n-1-i)=(n-1-i,n-1-j)
  
• f_next3=f(n-1-i,n-1-j)=(n-1-j,i)
  
• f_next4=f(n-1-j,i)=(i,j)
  发现规律，周期为4，意味着每四个结点一组交换位置即达到旋转效果

3. 为了避免重复旋转，接下来只需要确定每一组中哪一个节点做旋转即可

• 其实画到四阶矩阵就可以发现：
  假设我们从左上角开始：
  • 第一行的前n-1个位置都需要旋转操作
  • 第二行从第2个位置开始的n-2-1个位置需要操作 ……
  • 如果当前行n-2=1,则该组只有一个结点（四个位置重合了）不需要旋转

  归纳出:
  对于n阶矩阵，前(n+1)/2行需要旋转,从第一行开始，往下每行需要旋转的位置都减少2
  每行开始位置横纵下表相等

  • 代码中inner为当前有效基数（每行-2）

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        int idx=0;
        int inner=n;
        while(idx<=n/2-1&&inner>1){
            int col=idx;
            for(int i=1;i<inner;i++){
                swap(mat,idx,col,n);
                col++;
            }
            inner-=2;
            ++idx;
        }
        return mat;
    }
    
    public void swap(int[][] mat,int i, int j,int n){
        int temp=mat[i][j];
        mat[i][j]=mat[j][n-1-i];
        mat[j][n-1-i]=temp;
        temp=mat[i][j];
        mat[i][j]=mat[n-1-i][n-1-j];
        mat[n-1-i][n-1-j]=temp;
        temp=mat[i][j];
        mat[i][j]=mat[n-1-j][i];
        mat[n-1-j][i]=temp;
    }
}