时间戳

首页 > 解决方案 > nxn 方阵的一维表示的就地旋转

arrays - nxn 方阵的一维表示的就地旋转

问题描述

我有一个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) 空间，我们只需将原始索引映射到旋转索引并复制原始位置的条目。很简单。

但我想知道是否有一种方法可以就地执行方阵的一维表示。我知道有很好的二维表示算法......有什么建议吗？

标签： arraysmatrixrotationtransformlinear-algebra

解决方案

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

因此，例如旋转 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) );
}

推荐阅读