java - "rotating matrix"的代码是聪明的还是幼稚的？ O(1) 方法

Question

我只是在一些随机情况下遇到了矩阵旋转。最明显的方法是将元素从 (n x m) 矩阵 A 映射到 A'，其中 A' 是具有 (m x n) 的新矩阵。这是这个明显方法的一些伪代码，时间复杂度为 O(nm)。

def rotateRight(A[1..n][1..m]): // O(nm)
    let A'[1..m][1..n] be a new matrix
    for i from 1 to n:
        for j from 1 to m:
            A'[n-j][i] = A[i][j] // not sure if this is right
    return A'

上面的代码看起来很典型。但是，经过一番思考，我实际上认为我们可以做得更好。

矩阵只能有 4 个方向(北、东、南、西)，无论您如何旋转它。这是一个例子:

通过封装矩阵的内部表示并为元素提供getter方法，我们实际上可以像下面这样实现旋转。

class Matrix{
     private (final) elements[n][m];

     private getElemStrategies = [getElemNorth, getElemEast, getElemSouth, getElemWest];
     private currentStrategy = 0;

     public getElem(x, y){
         return getElemStrategies[currentStrategy];             
     }

     public rotateRight(){ // O(1)
         currentStrategy = (currentStrategy + 1) % 4
     }
}

这里的getElemNorth,getElemEast,getElemSouth,getElemWest只是对应当前方位的getter方法矩阵。具体来说，getElemEast 类似于:

def getElemEast(x, y)
    return this.elements[n-j][i]

这个方法需要 O(1)，它确实有效。我认为这很酷，但不确定其正确性。这个方法有名字吗？

Answer 1

这是一个非常标准的技术。

为了更好地阐述，我建议阅读 NumPy strides 的工作原理，例如 here .

对此要记住的一件事是引用的位置很重要:扫描内存中的连续位置比读取分散在各处的相同数量的数据要便宜得多。根据您对矩阵的处理方式，这可能会抵消恒定时间旋转所节省的成本。