回 帖 发 新 帖 刷新版面

主题:求助:有关数组的一个算法

给定数组a[0:n-1]以及一个正整数k(0<=k<=n-1),设计一个算法,将子数组a[0:k]和
a[k+1:n-1]交换位置,要求算法在最坏的情况下耗时O(n),且用到的辅助空间为O(1)。

回复列表 (共1个回复)

沙发

显然,你肯定知道a[x]-->a[y]中x和y的关系,这个很简单假设y=f(x)
那么,就这样
x=0;
while
{
y=f(x);
特例 (y==0)
{
    将a[x]的内容放入a[y]
    跳出。
}
将a[y]的内容放入tmp
将a[x]的内容放入a[y]
将tmp的内容放入a[x]
x=y;  //下次循环的时候,a[x]就是现在的tmp,就是此轮开始的时候的a[y]
}

想法就是,从第一个开始
把他放到相应的位置的时候挤出了那个位置上的人,然后接下来就安排这个人,
到相应的位置,又挤出一个人,直到最后一个人到了第一个位置

y和x的关系为
y= x+ (n-1)-k 如果x是从0~k
y= x - k 如果x是从k+1到n-1

我来回复

您尚未登录,请登录后再回复。点此登录或注册