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, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

解答

• 方法一

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);