旋转矩阵n次

Question

当我陷入困境时,我正在解决HackerRank上的问题.

问题陈述

您将获得一个2D矩阵,a,维度为MxN,正整数为R.您必须将矩阵旋转R次并打印结果矩阵.旋转应沿逆时针方向旋转.

4x5矩阵的旋转由下图表示.请注意,在一次旋转中,您必须仅将元素移动一步(请参阅样本测试以获得更清晰).

保证M和N的最小值是偶数.

输入

第一行包含三个空格分隔的整数,M,N和R,其中M是行数,N是矩阵中的列数,R是矩阵必须旋转的次数.然后是M行,其中每行包含N个空格分隔的正整数.这些M行代表矩阵.

产量

打印旋转的矩阵.

约束

2 <= M, N <= 300 
1 <= R <= 10^9 
min(M, N) % 2 == 0 
1 <= aij <= 108, where i ? [1..M] & j ? [1..N]'

我试图做的是将圆圈存储在一维数组中.像这样的东西.

 while(true)
    {
        k = 0;
        for(int j = left; j <= right; ++j) {temp[k] = a[top][j]; ++k;}
        top++;
        if(top > down || left > right) break;

        for(int i = top; i <= down; ++i) {temp[k] = a[i][right]; ++k;}
        right--;
        if(top > down || left > right) break;

        for(int j = right; j >= left; --j) {temp[k] = a[down][j] ; ++k;}
        down--;
        if(top > down || left > right) break;

        for(int i = down; i >= top; --i) {temp[k] = a[i][left]; ++k;}
        left++;
        if(top > down || left > right) break;
    }

然后我可以通过计算其模数为R的长度来轻松旋转1D矩阵.但是,我如何将其重新放回矩阵形式？再次使用循环可能会导致超时.

请不要提供代码,但只提供建议.我想自己做.

解决方案创建:

#include <iostream>
using namespace std;



int main() {
int m,n,r;
cin>>m>>n>>r;
int a[300][300];
for(int i = 0 ; i < m ; ++i){
    for(int j = 0; j < n ; ++j)
        cin>>a[i][j];
}

int left = 0;
int right = n-1;
int top = 0;
int down = m-1;
int tleft = 0;
int tright = n-1;
int ttop = 0;
int tdown = m-1;
int b[300][300];
int k,size;
int temp[1200];

while(true){
    k=0;
    for(int i = left; i <= right ; ++i)
    {
        temp[k] = a[top][i];
      //  cout<<temp[k]<<" ";
        ++k;
    }
    ++top;

    if(top > down || left > right) 
        break;

    for(int i = top; i <= down ; ++i)
    {
        temp[k]=a[i][right];
       // cout<<temp[k]<<" ";
        ++k;
    }
    --right;
    if(top > down || left > right) 
        break;

    for(int i = right; i >= left ; --i)
    {
        temp[k] = a[down][i];
      //  cout<<temp[k]<<" ";
        ++k;
    }
    --down;

    if(top > down || left > right) 
        break;

    for(int i = down; i >= top ; --i)
    {   
        temp[k] = a[i][left];
       // cout<<temp[k]<<" ";
        ++k;
    }

    ++left;
    if(top > down || left > right) 
        break;

    //________________________________\\

    size = k;
    k=0;
   // cout<<size<<endl;
    for(int i = tleft; i <= tright ; ++i)
    {
        b[ttop][i] = temp[(k + (r%size))%size];
     //   cout<<(k + (r%size))%size<<" ";
     //   int index = (k + (r%size))%size;
       // cout<<index;
        ++k;
    }
    ++ttop;

    for(int i = ttop; i <= tdown ; ++i)
    {
        b[i][tright]=temp[(k + (r%size))%size];
        ++k;
    }
    --tright;

    for(int i = tright; i >= tleft ; --i)
    {
        b[tdown][i] = temp[(k + (r%size))%size];
        ++k;
    }
    --tdown;

    for(int i = tdown; i >= ttop ; --i)
    {   
        b[i][tleft] = temp[(k + (r%size))%size];
        ++k;
    }

    ++tleft;
}

size=k;
k=0;
if(top != ttop){
    for(int i = tleft; i <= tright ; ++i)
    {
        b[ttop][i] = temp[(k + (r%size))%size];
        ++k;
    }
    ++ttop;
}
if(right!=tright){
    for(int i = ttop; i <= tdown ; ++i)
    {
        b[i][tright]=temp[(k + (r%size))%size];
        ++k;
    }
    --tright;
}
if(down!=tdown){
    for(int i = tright; i >= tleft ; --i)
    {
        b[tdown][i] = temp[(k + (r%size))%size];
        ++k;
    }
    --tdown;
}
if(left!=tleft){
    for(int i = tdown; i >= ttop ; --i)
    {   
        b[i][tleft] = temp[(k + (r%size))%size];
        ++k;
    }

    ++tleft;
}
for(int i = 0 ; i < m ;++i){
    for(int j = 0 ; j < n ;++j)
        cout<<b[i][j]<<" ";
    cout<<endl;
}

return 0;
}

Answer 1

你需要分解这个问题（让我想起gg和fb的一个面试问题）：

1. 解决首先将序列旋转一个位置的问题
2. 然后求解旋转序列 N 次
3. 将每个“圆”或环建模为一个数组。您实际上可能需要也可能不需要存储在单独的数据中
4. 迭代每个环并应用旋转算法

L让我们考虑需要旋转时间的长度数组的情况R。观察到，如果R是 的倍数L，则数组将保持不变。还要观察到向右旋转时间与向左x旋转时间相同（反之亦然）。L - x

1. 因此，您可以首先设计一种算法，能够向左或向右旋转一次恰好一个位置
2. R将向左旋转次数的问题减少为R modulo L向左旋转
3. R modulo L如果你想进一步将向左旋转的问题减少为向左旋转R modulo L或向右旋转L - R modulo L。这意味着如果你有 100 个元素并且必须向左旋转 99 次，那么最好向右旋转 1 次并完成。

因此复杂度将为 O（圆数 x 圆长 x 单次旋转成本）

就地数组意味着O( min(N,m) * (N * M)^2 )

如果使用双向链表作为临时存储，则通过删除前面并将其放在尾部来完成单个旋转序列（反之亦然以向右旋转）。所以你能做的就是先将所有数据复制到一个链表中。运行单次旋转算法R modulo L多次，将环位置上的链表复制回，然后向右移动，直到处理完所有环。

• 将数据复制ring到列表是O(L), L <= N*M
• 单轮旋转成本为 O(1)
• 所有旋转R modulo L都是O(L)
• 对所有重复min(N,m) rings

使用备用双链表意味着复杂性O( min(N,m) * (N * M))