时间戳

首页 > 解决方案 > 二维矩阵能否以比 O(n^2) 更好的时间复杂度旋转 90°？

algorithm - 二维矩阵能否以比 O(n^2) 更好的时间复杂度旋转 90°？

问题描述

这是矩阵旋转的示例输入/输出：

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

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

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

标签： algorithmtime-complexity

解决方案

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

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

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

下面是这个想法在 JavaScript 中的简单演示。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());
}

推荐阅读