以同心圆旋转 2D NxN 矩阵

Question

给定一个 2D NxN 矩阵，将其可视化为同心圆。您必须找到旋转矩阵，其中圆中的每个元素以顺时针和逆时针方向交替旋转 1 个位置。所有旋转都应就位。

2 3 4 5
1 6 7 8
4 2 1 9
5 3 2 4

应该转变为

1 2 3 4 
4 7 1 5 
5 6 2 8 
3 2 4 9 

我思考了解决方案

1> 顺时针旋转，按顺序读取元素

i -> 0 to n-1 and j = 0
j -> 0 to n-1 and i = n-1
i -> n-1 to 0 and j = n-1
j -> n-1 to 0 and i = 0

2> 逆时针旋转，按顺序读取元素

j -> 0 to n-1 and i = 0
i -> 0 to n-1 and j = n-1
j -> n-1 to 0 and i = n-1
i -> n-1 to 0 and j = 0

代码

for(int cnt = 0; cnt < n/2; cnt++)
    {   
        if(cnt%2 == 0) // Clockwise
        {   
            i = cnt; j = cnt;
            // while loops for each case
        }
        else // anti-clockwise
        {
            i = cnt; j = cnt;
            // while loops for each case
        }       
}

有没有更好的方法可以在 O(n2) 或更好的时间内解决这个问题？

Answer 1

由于数组的大小为 N*N 并且所需的计算要求每个元素至少被访问一次，因此没有比O(n^2)使用二维数组更好的解决方案。

我认为如果必须在同一个数组上执行一次操作，您的解决方案会很好。

如果必须对同一输入数组多次执行此操作，最好从输入数组创建圆圈。Circle的数据结构应该是CLL（循环链表）。因此，多次执行该操作将是小菜一碟，因为您必须根据方向更改存储圆信息的 CLL 的根元素。