首页 > 试题广场 >

题目来源于王道论坛设将n（n1）个整数存放到一维数

[问答题]

题目来源于王道论坛

设将n（n>1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据由（X₀, X₁,, X_n_-₁）变换为（X_p, X_p+1,, X_n_-₁, X₀, X₁,, X_p_-₁）。要求：

1）给出算法的基本设计思想。

2）根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。

3）说明你所设计算法的时间复杂度和空间复杂度。

推荐

林呼

1）算法的基本设计思想：

可以将这个问题看作是把数组ab转换成数组ba（a代表数组的前p个元素，b代表数组中余下的n-p个元素），先将a逆置得到a^-¹b，再将b逆置得到a^-¹b^-¹，最后将整个a^-¹b^-¹逆置得到（a^-¹b^-¹）^-¹=ba。设Reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3（p=3）个位置的过程如下：

Reverse(0,p-1)得到cbadefgh；

Reverse(p,n-1)得到cbahgfed；

Reverse(0,n-1)得到defghabc。

注：Reverse中，两个参数分别表示数组中待转换元素的始末位置。

2）使用C语言描述算法如下：

void Reverse(int R[],int from,int to) {
    int i,temp;
    for(i=0;i<(to-from+1)/2;i++)
    {    temp=R[from+i];R[from+i]=R[to-i];R[to-i]=temp;}
}//Reverse
void Converse(int R[],int n,int p){
    Reverse(R,0,p-1);
    Reverse(R,p,n-1);
    Reverse(R,0,n-1);
}

3）上述算法中3个Reverse函数的时间复杂度分别为O(p/2)、O((n-p)/2)和O(n/2)，故所设计的算法的时间复杂度为O(n)，空间复杂度为O(1)。

另解，借助辅助数组来实现。

算法思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。

时间复杂度为O(n)，空间复杂度为O(p)。

发表于 2018-09-03 20:24:04 回复(0)