48 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

题解

我们观察规律， 举例来说

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

旋转90度后

13 9  5 1
14 10 6 2
15 11 7 3
16 12 8 4

比如说 14 的位置是 第四行第二列，旋转后位置是第二行第一列

那么假设现在有一个元素 matrix[i][j]，它现在的位置是第i行第j列，那么它旋转90度后，正好变成了倒数第j行第i列。

所以我们得出结论

matrix[i][j] = matrix[n-j-1][i]

解法1 复制矩阵

那么第一种解法，利用上面的公式，我们可以复制出一个旋转过后的矩阵。然后再将原矩阵赋值为旋转过后的矩阵。

var rotate = function(matrix) {
    var newMatrix = []
    //利用 matrix[i][j] = matrix[n-j-1][i] 来复制
    for (let i = 0; i < matrix.length; i++) {
        newMatrix.push(Array(matrix[i].length).fill(undefined))
        for (let j = 0; j < matrix[i].length; j++) {
            newMatrix[i][j] = matrix[matrix.length - j - 1][i];
        }
    }
    //然后复制
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[i].length; j++) {
            matrix[i][j] = newMatrix[i][j]
        }
    }
}

解法2 原地旋转

我们能不能只使用一个temp 来旋转呢，按照上面的公式 matrix[i][j] 会被 matrix[n-j-1][i] 覆盖。 matrix[n-j-1][i] 会被 matrix[n-i-1][n-j-1] 覆盖 matrix[n-i-1][n-j-1] 会被 matrix[j][n-i-1] 覆盖。 matrix[j][n-i-1] 会被 matrix[i][j] 覆盖。 所以这个形成了一个闭环，我们可以利用temp 来保存matrix[i][j]的值，然后替换四次。

接下来的问题是如何遍历。对于偶数行矩阵来说，我们只需遍历1/4的区域即可。对于奇数行矩阵来说，行需要遍历1/2行数，列数需要遍历 1/2 + 1 列数。

可以看官方的题解图片。

var rotate = function(matrix) {
    // 根據上面的公式
    // matrix[i][j] 的新位置 matrix[n-j-1][i]
    // matrix[n-j-1][i] 的新位置 matrix[n-i-1][n-j-1]
    // matrix[n-i-1][n-j-1] 的新位置 matrix[n-[n-j-1] -1][n-i-1] -> matrix[j][n-i-1]
    // matrix[j][n-i-1]的新位置 matrix[n-[n-i-1] - 1][j] -> matrix[i][j]
    // 这样来说就是一个循环
    // 设 temp = matrix[i][j],
    // matrix[i][j] = matrix[n-j-1][i],
    // matrix[n-j-1][i] = matrix[n-i-1][n-j-1],
    // matrix[n-i-1][n-j-1] = matrix[j][n-i-1]
    // martix[j][n-i-1] = temp

    //循环的条件, 对于n 是偶数 循环次数为 n/2,  n是奇数，第一轮循环为n/2, 第二轮循环是(n+1)/2
    // 可以合并一下， 第一轮循环为 n/2, 第二轮循环为 (n+1)/2
    const n = matrix.length
    for (let i = 0; i < Math.floor(n / 2); i++) {
        for (let j = 0; j < Math.floor((n + 1) / 2); j++) {
            const temp = matrix[i][j]
            matrix[i][j] = matrix[n - j - 1][i]
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
            matrix[j][n - i - 1] = temp
        }
    }
}