2D 矩阵是否可以以比 O(n^2) 更好的时间复杂度旋转 90°？

Question

这里有一个矩阵旋转的例子input/output：

Input: [[1,2,3,],[4,5,6],[7,8,9]]
Output: [[7,4,1], [8,5,2], [9,6,3]]

我知道旋转可以用 O(n^2) 的时间复杂度来执行。

有没有更快的解决方案？会是什么？

Answer 1

不，width/height n 的矩阵不能以比 O(n²) 更好的时间复杂度进行旋转。这是因为有 O(n²) 个值需要移动。

但是，有一种方法可以解决这个问题：

您可以决定不真正执行轮换，而只是对轮换进行注释，并将任何后续访问转换为矩阵相应。如果你这样做，那么矩阵旋转具有 O(1) 时间复杂度。

这是 JavaScript 中该想法的简单演示。 class Matrix 应使用您想要支持的所有方法进行扩展（如 set、invert、determinant、...等），其中每个方法都将必须考虑到这种特殊性。但这不会影响他们自己的时间复杂度。

class Matrix {
    constructor(rows) {
        // Take a copy of the 2d-array passed as argument
        this.rows = [];
        for (let row of rows) {
            this.rows.push(Array.from(row));
        }
        this.rotation = 0;
        this.n = rows.length;
    }
    rotate90() {
        this.rotation = (this.rotation + 1) % 4;
    }
    get(rowIdx, colIdx) {
        switch (this.rotation) {
        case 0: return this.rows[rowIdx][colIdx];
        case 1: return this.rows[this.n-1-colIdx][rowIdx];
        case 2: return this.rows[this.n-1-rowIdx][this.n-1-colIdx];
        case 3: return this.rows[colIdx][this.n-1-rowIdx];
        }
    }
    toString() {
        let txt = "";
        for (let rowIdx = 0; rowIdx < this.n; rowIdx++) {
            txt += "\n";
            for (let colIdx = 0; colIdx < this.n; colIdx++) {
                txt += " " + this.get(rowIdx, colIdx);
            }
        }
        return txt.slice(1);
    }
}


// Demo
let m = new Matrix([[1,2,3],[4,5,6],[7,8,9]]);

console.log(m.toString());

for (let rot = 1; rot <= 4; rot++) {
    m.rotate90();
    console.log(m.toString());
}

2D 矩阵是否可以以比 O(n^2) 更好的时间复杂度旋转 90°？

Can 2D matrix be rotated with 90° in a better time complexity than O(n^2)?

algorithm

time-complexity