Rotate Matrix

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

You need to do this in place.

Note that if you end up using an additional array, you will only receive partial score.

If the array is

[
    [1, 2],
    [3, 4]
]

Then the rotated array becomes:

[
    [3, 1],
    [4, 2]
]

思路:

我们可以发现，将一个nxn的矩阵顺时针转90度相当于将这个矩阵沿X = Y对换，然后再沿中轴线对换。
比如
1 2 3
4 5 6
7 8 9
   ||
9 6 3
8 5 2
7 4 1
   ||
7 4 1
8 5 2
9 6 3

Solution:

Time: O(n*n)
Space: O(1)

public class Solution {
    public void rotate(ArrayList<ArrayList<Integer>> a) {
        /*
            1 2 3
            4 5 6
            7 8 9
            
            9 6 3
            8 5 2
            7 4 1
            
            7 4 1
            8 5 2
            9 6 3
        */
        swapAroundXY(a);
        swapAroundMidHorizontal(a);
    }
    
    // y = - x + (n - 1);
    private void swapAroundXY(ArrayList<ArrayList<Integer>> a) {
        int n = a.size();
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                if (j == - i + (n - 1)) break;
                swap(a, i, j, n - 1 - j, n - 1 - i);
            }
        }
    }
    
    private void swapAroundMidHorizontal(ArrayList<ArrayList<Integer>> a) {
        int n = a.size();
        for (int i = 0; i < n / 2; i ++) {
            for (int j = 0; j < n; j ++) {
                swap(a, i, j, n - 1 - i, j);
            }
        }
    }
    
    private void swap(ArrayList<ArrayList<Integer>> a, int i, int j, int x, int y) {
        int temp = a.get(i).get(j);
        a.get(i).set(j, a.get(x).get(y));
        a.get(x).set(y, temp);
    }
}