我有一个表示为一维数组的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) );
}