Question

求解一道数据结构题目

设计一个时间复杂度为O(n)的算法，实现将数组A[n]中所有元素循环右移k个位置。

Answer 1

#include <iostream>
using namespace std;

//array 数组A
//n 数组长度
//k 移动距离

int* Move(int* array,int n,int k)
{
int* temp=new int[n];
int i,j;
//如果小于0，则警告，同时数组不改变
if(k<0){cout<<"warn: k<0,the array is not changed!!"<<endl;return array;}
//如果移动位数比数组元素个数多，则进行处理。
if(k>=n)k=k%n;
//将n－k位前的数组元素移动到第k位
for(i=0,j=n-k;j<=n-1;i++,j++)
temp[i]=array[j];
//将n-k位前的数组元素补上
for(j=0;j<=n-k-1;j++,i++)
temp[i]=array[j];
delete(array);
array=temp;
return array;
}

int main()
{
int i;
//测试用的 声明了一个10个元素的数组A[10]
int* A=new int[10];
//为每个元素赋值
for(i=0;i<10;i++)A[i]=i;
//调用函数，移动k=25位
A=Move(A,10,25);
//输出结果
cout<<"result:"<<endl;
for(i=0;i<10;i++)cout<<A[i]<<endl;
return 0;
}