# 48. Rotate Image

### Leetcode

#### <https://leetcode.com/problems/rotate-image/>

### 題目

You are given an `n x n` 2D `matrix` representing an image, rotate the image by **90** degrees (clockwise).

You have to rotate the image [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm), which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation.

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

&#x20;<img src="https://3511771902-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MjUa_JpTZ6O63Qvohud%2F-MkSfEru4XmdXZhddW8C%2F-MkSgYqnLFHhqx6D_Yv1%2F%E6%88%AA%E5%9C%96%202021-09-26%20%E4%B8%8A%E5%8D%8812.02.50.png?alt=media&#x26;token=cd88c1d4-1dd6-4e1e-88f4-79854c6a9cf0" alt="" data-size="original">&#x20;

5 <-> 15，2 <-> 14，13 <-> 12 互相調換，從最外圈依序往內，每圈調換三次後可完成

```
var rotate = function(matrix) {
    const n = matrix.length;
    // 總共有幾圈
    let round = Math.floor(n/2);

    const swap = (x1, y1, x2, y2) => {
        let temp = matrix[x1][y1];
        matrix[x1][y1] = matrix[x2][y2];
        matrix[x2][y2] = temp;
    }
    
    while(round>0) {
      const start = Math.floor(n/2) - round;
      const end = n-1-start;
      // 標記左上、左下、右下位置
      const initArr = [
          {x1: start, y1: start, x2: end, y2: start},
          {x1: end, y1: start, x2: end, y2: end},
          {x1: end, y1: end, x2: start, y2: end}
      ]
      for (let i=0; i<initArr.length; i++) {
          let {x1, y1, x2, y2} = initArr[i];
          for(let j=0; j<n-1-start*2; j++) {
              swap(x1, y1, x2, y2);
              if(i===0) {
                  x1++;
                  y2++;
              }
              if(i===1) {
                  y1++;
                  x2--;
              }
              if(i===2) {
                  x1--;
                  y2--;
              }
          }
      }
      round--;
    }
};
```

Runtime: 110 ms, faster than 15.93% of JavaScript online submissions for Rotate Image.

Memory Usage: 38.6 MB, less than 85.66% of JavaScript online submissions for Rotate Image.

* **方法二**

先對角線鏡射交換，再沿著 y-axis 對換

*p.s.* x 的方向 \[5, 1, 9, 11]， y 的方向 \[5, 2, 13, 15]

```
var rotate = function(matrix) {
    const n = matrix.length;

    const swap = (x1, y1, x2, y2) => {
        let temp = matrix[x1][y1];
        matrix[x1][y1] = matrix[x2][y2];
        matrix[x2][y2] = temp;
    }

    // 對角線交換
    for(let i=0; i<n; i++) {
      for(let j=i+1; j<n; j++) {
        swap(i, j, j, i);
      }
    }

    // y-axis 方向對換
    for(let i=0; i<n; i++) {
      for(let j=0; j<Math.floor(n/2); j++) {
        swap(i, j, i, n-1-j);
      }
    }
};
```

Runtime: 80 ms, faster than 41.39% of JavaScript online submissions for Rotate Image.

Memory Usage: 38.1 MB, less than 98.14% of JavaScript online submissions for Rotate Image.

(更進一步對時間的優化可以在第一次的兩層 for 迴圈中，直接把對角線跟 y-axis 交換一併處理掉)

### 測資

```
let matrix = [[1]];
matrix = [[1,2],[3,4]];
matrix = [[1,2,3],[4,5,6],[7,8,9]];
matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]

rotate(matrix);
console.log(matrix);
```
