旋转二维数组而不使用新数组 - 最佳C++解决方案？

Question

我的一个学生向我提出了这样的C++数组作业问题。它对我来说似乎很有趣，所以尽管我已经解决了这个问题，我还想与你分享我的解决方案，并知道其他变体和观点。问题如下：

问题 给定一个二维动态正方形矩阵（数组）A（n×n）。要求将数组逆时针旋转90度，即旋转后A [1,1]字段应包含A [1,n]的值，A [1,n]字段应包含A [n,n]的值。并且要求在解决此问题时不使用任何其他数组。

我的解决方案 我告诉学生按以下方式操作（将步骤用图表表示）：
我建议定义一个类，其成员将具有2D数组。并定义一个操作，当用户请求A [i，j] 时，该操作将返回对A [j，n + 1-i] 元素的引用。简而言之，我建议为数组创建一个包装器，并通过包装器操纵数组。

- Narek

---

你的解决方案实际上并没有解决问题。你只是为每个查询返回正确的元素，但实际上你并没有像问题所要求的那样对它们进行旋转。不过这是一个有趣的问题，加一分。 - IVlad

@IVlad：实际上，解决问题是一个观点问题。你可以非常确定这就是像Matlab这样的程序实现矩阵转置的方式，只需使用状态和适当的获取器，没有真正的转换。当然，我怀疑我的老师们不会在考试中接受这个答案:D。 - KillianDS

注意！！！所有这些解决方案都使用了一个新数组！解决方案应该不使用新数组。 - Narek

@nikhil 别太心疼啦！:) 我告诉他们了正确的解决方案，当然！你可能会为那些老师建议权宜之计并通过问题，而没有提供更好的解决方案的学生感到可怜 ;) - Narek

我非常感激你寻找更好的解决方案，同时我也没有任何意图伤害个人。我会删除我的评论。对此表示抱歉。 - nikhil

Answer 1

维基百科上有一篇关于原地矩阵转置的文章。

考虑以下内容：

a b c
e f g
x y z

transpose:
a e x
b f y
c g z

rotated 90 deg CCW:
c g z
b f y
a e x

在转置矩阵之后，反转行就可以轻松地原地完成。

- IVlad

---

等等，那就是我写的！但既然这个更清晰，我就把我的删掉。并且 +1 :-) - Aryabhatta

@Moron：我自己也经常遇到这个问题，可能是我太慢了 :D - Matthieu M.

@Matthieu： :-) 我猜测这与stackoverflow的实现方式有关（缓存等）。因此，即使我在发布这个问题之前2-3分钟已经发布了答案，也许对其他人来说并不同时可见。无论如何，我的回答非常简洁，而这个回答更好地解释了为什么这种方法有效。 - Aryabhatta

Answer 2

您可以使用“四向交换”和嵌套循环以及一些旋转技巧（在纸上计算出来）来解决问题：

template <typename T>
void swap(T& a, T& b, T& c, T& d)
{
    T x(a);
    a = b;
    b = c;
    c = d;
    d = x;
}

template <typename T, size_t dim>
void rotate(T (&matrix)[dim][dim])
{
    const size_t d = dim-1;
    for (size_t y = 0; y < dim/2; ++y)
    {
        for (size_t x = y; x < d-y; ++x)
        {
            swap(matrix[y  ][x  ],
                 matrix[x  ][d-y],
                 matrix[d-y][d-x],
                 matrix[d-x][y  ]);
        }
    }
}

测试程序：

template <typename T, size_t dim>
void print(T (&matrix)[dim][dim])
{
    for (size_t y = 0; y < dim; ++y)
    {
        for (size_t x = 0; x < dim; ++x)
        {
            std::cout << matrix[y][x] << ' ';
        }
        std::cout << '\n';
    }
}

int main()
{
    int matrix[4][4] = {{1, 2, 3, 4},
                        {5, 6, 7, 8},
                        {9, 10, 11, 12},
                        {13, 14, 15, 16}};
    rotate(matrix);
    print(matrix);
}

输出：

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

现在你只需要将它从模板形式转换为动态形式即可 ;)

- fredoverflow

---

递归算法可能更加优雅和简洁。 - Snicolas

Answer 3

很抱歉，这并不是C++而是Java。以下是一个使用简单数组支撑的递归算法，代码如下：

public void rotateInPlaceRecursive() {
    if( rowCount != colCount ) {
        throw new IllegalStateException("Matrix must be square");
    }
    doRotateInPlaceRecursive(0);
}

public void doRotateInPlaceRecursive(int shrink) {
    if( shrink == rowCount/2 ) {
        return;
    }
    for (int col = shrink; col < colCount-shrink-1; col++) {
        int row = shrink;
        int top     = tab[row][col];
        int left    = tab[rowCount-col-1][row];
        int bottom  = tab[rowCount-row-1][rowCount-col-1];
        int right   = tab[col][rowCount-row-1];

        tab[row][col] = right;
        tab[rowCount-col-1][row] = top;
        tab[rowCount-row-1][rowCount-col-1] = left;
        tab[col][rowCount-row-1] = bottom;

    }
    doRotateInPlaceRecursive(shrink+1);
}

---- 测试

@Test
public void testRotateInPlaceRecursive() {
    // given
    int N = 5;
    Matrix matrix = new Matrix(N, N);

    // when
    int i=0;
    for( int row = 0; row< N; row++ ) {
        for( int col = 0; col< N; col++ ) {
            matrix.set(row,col, i++ );
        }
    }

    // then
    matrix.rotateInPlaceRecursive();
    i = 0;
    for( int row = 0; row< N; row++ ) {
        for( int col = 0; col< N; col++ ) {
            assertEquals(i++,matrix.get(N-col-1,row));
        }
    }
}

- Snicolas

Answer 4

以下示例是Java示例，可以轻松地采用到C++中。在内存中旋转大型矩阵可能会消耗大量资源，特别是当矩阵的值是复杂对象时。在这种情况下，通过函数重新计算索引，将它们重定向到旋转矩阵的元素，而不进行实际的旋转，可能更加高效。

public class RotateArray {

public static char arr[][] = { { 'a', 'b', 'c','1' }, { 'd', 'e', 'f','2' }, { 'g', 'h', 'i','3' },{ 'j', 'k', 'l','4' } };
private static int imax = arr.length-1;
private static int jmax = arr[0].length-1;

public static void printArray() {

    for (int i = 0; i <= imax; i++) {
        for (int j = 0; j <= jmax; j++) {
            System.out.print(arr[i][j] + " ");
        }
        System.out.print("\n");
    }
}

public static void printRotatedArray() {
    for (int i = 0; i <= imax; i++) {
        for (int j = 0; j <= jmax; j++) {
            System.out.print(arr[getRotatedI(i,j)][getRotatedJ(i,j)] + " ");
        }
        System.out.print("\n");
    }
}   

public static int getRotatedI(int i,int j){     
    int ii = imax-j;
    return ii;
}

public static int getRotatedJ(int i,int j){
    int jj = i;
    return jj;
}       

public static void main(String[] args) {

    System.out.println("Printing matrix");
    printArray();
    System.out.println("Printing rotated matrix");
    printRotatedArray();
}

}

输出：

Printing matrix
a b c 1 
d e f 2 
g h i 3 
j k l 4 

Printing rotated matrix
j g d a 
k h e b 
l i f c 
4 3 2 1

- Nikolay Frick

Answer 5

O(n^2) 时间复杂度和 O(1) 空间复杂度的算法（没有任何变通或奇怪的东西！）

顺时针旋转90度：

Transpose
Reverse each row

旋转-90度：

Transpose
Reverse each column

旋转 +180 度：

方法 1：先旋转 +90 度，再旋转一次

方法 2：先翻转每一行，再翻转每一列

旋转 -180 度：

方法 1：先旋转 -90 度，再旋转一次

方法 2：先翻转每一列，再翻转每一行

方法 3：因为和旋转 +180 度相同，所以可以通过旋转 +180 度来实现

- rahul