旋转同心圆二维N×N的矩阵

问题描述

给定一个N×N的二维矩阵，它想象为同心圆。你必须找到，其中在圈内的每个元素由1位层以交替顺时针和逆时针方向旋转时由层旋转矩阵。所有的轮换应该在的地方。

Given a 2D NxN matrix, visualize it as concentric circles. You have to find the rotated matrix where each element in the circle is rotated by 1 position layer by layer in an alternate clockwise and anticlockwise direction. All rotations should be in-place.

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

我想到了解决办法

I thought about the solution

1>顺时针旋转一圈，阅读的顺序元素

1> For clockwise circle rotation, read elements in the order

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>对于逆时针旋转一圈，阅读的顺序元素

2> For anti-clockwise circle rotation, read elements in the order

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

code

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），或者这个问题比较好？

Is there any better approach to solve this problem in O(n2) or better ?

推荐答案

由于阵列是大小为N * N和所需的计算要求每个元素被ATLEAST访问一次，不能有一个解决方案比<$ C $更好C>为O（n ^ 2）它采用2维数组。

As your array is of size N*N and the desired computation demands each element to be visited atleast once, there cannot be a solution better than O(n^2) which uses 2 dimensional arrays.

我认为您的解决方案将是罚款，如果操作必须要在同一个阵列上完成一次。

I think that your solution will be fine if the operation has to be done single time on the same array.

如果你有多次做此操作相同的输入阵列上，更好地创造从输入数组圈。圆的数据结构应该是一个慢性淋巴细胞白血病（循环链表）。这样操作多次​​将是一块蛋糕，你必须改变CLL的根元素存储在不同的方向的圆圈信息。

If you have to do this operation multiple times on the same input array, better create circles from the input array. The data structure of circle should be a CLL (circular linked list). So doing the operation multiple times will be piece of cake as you have to change the root element of the CLL storing the circle info depending on the direction.

这篇关于旋转同心圆二维N×N的矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！