n x n 方阵的一维表示的就地旋转



我有一个表示为一维数组的n x n矩阵。左上角以索引 0 开头。索引 i 计算为 i = x * n + y其中 x 和 y 是二维表示中矩阵条目的索引。

对于 n = 4

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

要顺时针旋转 90 度,我们得到

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

映射现已i = 12 + y - (n * x)

使用 O(n^2( 空间,我们只需将原始索引映射到旋转索引,然后复制原始位置的条目。很简单。

但是我想知道有没有办法就地为方阵的一维表示做到这一点。我知道有很好的 2-D 表示算法......有什么建议吗?

任何旋转都可以分解为两个不同轴上的两个连续反射。在您的情况下,可以通过交换矩阵的元素来完成反射。因此,它可以就地完成。

例如,对于旋转 90 度,第一次反射可以围绕 x 轴完成,将第一行与最后一行交换,然后将第二行与第三行交换,您可以得到:

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

现在第二个反射是围绕主对角线,就像矩阵的转置一样,以对称的方式在对角线上交换元素:

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

这两个反射都可以迭代地交换各个元素,因此它们可以就地完成。如果矩阵是 1D 还是 2D,它不会受到影响。

C++ 就地旋转的示例(矩阵的一维数组表示形式(:

const int ROWS = 4;
const int COLS = ROWS;
int A[ROWS*COLS];
int index(int row, int col) { return col + COLS * row; }
void swap(int i, int j) { int a = A[i]; A[i] = A[j]; A[j] = a; }
// x-axis reflection
for(int row_i = 0 ; row_i < ROWS / 2; ++row_i) {
    int row_j = ROWS - row_i - 1;
    for(int col_i = 0 ; col_i < COLS ; ++col_i)
        swap( index(row_i, col_i), index(row_j, col_i) );
}
// diagonal reflection
for(int row_i = 0 ; row_i < ROWS; ++row_i) {
    for(int col_i = row_i + 1 ; col_i < COLS ; ++col_i)
        swap( index(row_i, col_i), index(col_i, row_i) );
}

相关内容

  • 没有找到相关文章

最新更新