首页 > 代码库 > 【算法编程】循环右移一个数组

【算法编程】循环右移一个数组

2024-07-02 17:48:57   227人阅读

仅用一个辅助节点将一个大小为n数组循环右移k位的三种办法：
1、时间复杂度最大：将所有元素每次只移动一位，总共移动k次，程序实现十分容易，在此就不具体实现了。
2、时间复杂度适中：依次将每个元素都放到辅助节点上，然后将其储存到目的节点,具体程序如下：
#include<iostream>
using namespace std;
int gcd(int x,int y);
int main()
{
        int n,k;
        cout<<"请输入数组的维数"<<endl;
        cin>>n;
        int *p=new int[n];
        for(int i=0;i<n;i++)
        {
                p[i]=i;
        }
        cout<<"请输入移动的位数"<<endl;
        cin>>k;
        k=k%n;
        int num=gcd(n,k);
        if(num==1)
        {
        int j=0;
        int temp=p[j];
        for(int i=0;i<n;i++)
        {
                j=(j+k)%n;
                temp=temp+p[j];
                p[j]=temp-p[j];
                temp=temp-p[j];
        }
        }
        else
        {
                for(int i=0;i<num;i++)
                {
                        int j=i;
                        int temp =p[i];
                        for(int ii=0;ii<n/num;ii++)
                        {
                                j=(j+k)%n;
                                temp=temp+p[j];
                                p[j]=temp-p[j];
                                temp=temp-p[j];
                        }
                }
        }
        for(i=0;i<n;i++)
        {
                cout<<p[i]<<" ";
        }
        cout<<endl;
        return 0;
}
int gcd(int x,int y)    //欧几里得辗转相除法求两数的最大的公约数
{
if(x<y)
        return gcd(y,x);
if(x%y!=0)
        return gcd(y,x%y);
else return y;
}
3、时间复杂度最小，总共只移动n+1次，具体思路如下：首先将一个元素放入辅助节点，由于要移动k位，肯定有一个元素会移动到刚才的节点，以此类推，最后肯定会空余一个节点，然后将辅助节点的元素放入即可。具体程序实现如下：
#include<iostream>
using namespace std;
int gcd(int x,int y);
int main()
{
        int n,k;
        cout<<"请输入数组的维数"<<endl;
        cin>>n;
        int *p=new int[n];
        for(int i=0;i<n;i++)
        {
                p[i]=i;
        }
        cout<<"请输入移动的位数"<<endl;
        cin>>k;
        k=k%n;
        int num=gcd(n,k);
        if(num==1)
        {
                int j=0;
                int temp=p[0];
                for(int i=0;i<n-1;i++)
                {
                        p[j]=p[(j+n-k)%n];
                        j=(j+n-k)%n;
                }
                p[(n-1)*(n-k)%n]=temp;
        }
        else
        {
                for(int i=0;i<num;i++)
                {
                        int j=i;
                        int temp =p[j];
                        for(int ii=0;ii<n/num-1;ii++)
                        {
                                p[j]=p[(j-k+n)%n];
                                j=(j-k+n)%n;
                        }
                        p[((n/num-1)*(n-k)+i)%n]=temp;
                }
        }
        for(i=0;i<n;i++)
        {
                cout<<p[i]<<" ";
        }
        cout<<endl;
        return 0;
}
int gcd(int x,int y)   
        //欧几里得辗转相除法求两数的最大的公约数
{
        if(x<y)
                return gcd(y,x);
        if(x%y!=0)
                return gcd(y,x%y);
        else return y;
}


联系
我们