class Solution {
    public void rotate(int[][] matrix) {
        // 题目要求需要原地旋转，不能新建数组
        // 直接matrix[col][n-1-row] = matrix[row][col]的交换会导致原位置的值被覆盖，后续的交换无法进行
         //两步实现：1.转置matrix,使得matrix[i][j]变为matrix[j][i]
         //2.将matrix[j][i] 与 matrix[j][n-1-i]交换
         // 先转置或者先交换行都一样，需要注意的是：交换和转置的边界
        int n = matrix.length;
        for (int row = 0; row < n / 2; row++) {
            for (int col = 0; col < n; col++) {
                int temp = matrix[row][col];
                matrix[row][col] = matrix[n - 1 - row][col];
                matrix[n - 1 - row][col] = temp;
            }
        }
        for (int row = 0; row < n ; row++) {
            for (int col = row; col < n; col++) {
                int temp = matrix[row][col];
                matrix[row][col] = matrix[col][row];
                matrix[col][row] = temp;
            }
        }
        
        
    }
}