48. Rotate Image

給一個n*n的矩陣，將其順時針旋轉90度。必須在原有的矩陣上作業，不可新增矩陣。

https://leetcode.com/problems/rotate-image/

範例
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

因為必須在原有矩陣上作業，故需要將矩陣內元素進行交換。

觀察後可以找到以下變換的規律。

基本上每個轉換都是4個為一組來交換，我們可以根據點位和四個角的相對位置，取得公式。

用代數來表示。
上圖藍色為四角的基準點，黃色代表其中的一組交換組合，綠色箭頭代表相對位移的量。
就可以知道n*n矩陣，假如任取一點[i,j]，可以推算出交換的點位為
[i,j] , [j,n-i] , [n–i,n-j] , [n–j,i]

先把這段寫成程式碼

	public void blockChange(int[][] matrix, int i, int j) {
		int temp = 0;
		int n = matrix.length - 1;

		temp = matrix[i][j];
		matrix[i][j] = matrix[n - j][i];
		matrix[n - j][i] = matrix[n - i][n - j];
		matrix[n - i][n - j] = matrix[j][n - i];
		matrix[j][n - i] = temp;
	}

再來只需要知道矩陣中有那些元素需要調換，丟入此方法中即可。

從可以5*5來觀察，將圖型看成一圈圈(紅框與紅框間)，
能發現每一圈只要從邊角起始，一直到n-1的位置進行調換，就能將整圈轉置。
因此可寫出以下程式

	public void rotate(int[][] matrix) {

		int x = 0;
		int j = 0;
		int n = matrix.length - 1;

		// 先從最外圈進行轉置
		while (n >= 1) {
			for (int i = x; i < n; i++) {
				blockChange(matrix, i, j);
			}
			// 往內部移動
			n = n - 1;
			x = x + 1;
			j = j + 1;
		}
	}