September 17, 2006

谈谈数组元素左旋问题(上)

终于把《编程珠玑》那本书给买来了。第一章2.3提出了一个“数组元素左旋问题”,《程序员》杂志上出过,描述如下:
对于有K个元素的数组int a[K] = {...},写一个高效算法将数组内容循环左移m位。比如:int a[6] = {1,2,3,4,5,6}循环左移3位结果是{4,5,6,1,2,3}。注:不允许返回其它内存空间,但可使用少许变量。
《程序员》上面给的解答抄自书后答案,网友给出的两次倒排算法抄自书上解法1~~晕死。
对于这个问题有已经有不少解决办法了。我上个星期教网友算法时讲到了这个问题,现在把这些算法整理出来罢。
先将一个不符合要求但很基本的想法:先在数组后扩充数组的前一部分,然后再删掉数组自己的前一部分。
用Python表示一下:
def move(a,m):
a.extend(a[:m])
return a[m:]

这个算法用C来实现我用了溢出的方法获得了更多内存(没必要管它能否通过编译),然后直接返回一个假的数组首地址。
int * move (int *a, int k, int m){
for (int i = 0; i <>
*(a+k+i) = *(a+i);
}
return (a+m-1);
}
很甩是不是?太猥琐了(但它说明了一个问题:大家都赞扬动态语言灵活,其实C也很灵活)。
更合适一点的做法是用一个线形数据结构保存前半部,再将原数组左移,最后将前半部分加回去。用Python表示一下(其实和上面那个也没多大区别):
def move (a, m):
j = i = 0
tmp = []
while i <>
tmp[i] = a[i]
a[i] = a[i+m]
i += 1
while j <>
a[j+m] = tmp[j]
i += 1
return a #其实数组已改变,这句可以不要
后悔了——实在是没有比这更别扭的Python代码了~~改成C就免了吧,初始化tmp是把长度设为m,编译时要加这个参数:-std=c99(gcc)。
好了,我就不再无聊了,开始讲点正经的吧:在原数组上操作。
先回忆一下冒泡排序法:当处理一个处在最左边但又是最大的项时,这个项是怎样移动的?
在纸上画一画——哦,它和每个元素交换,然后到了最右边…
…等等,呓?其它的项的顺序都没有变?!整个数组左移了!
那么,我们第一个符合要求的答案就出来了:把数组当成是反排序的,从最左边进行m次冒泡即可!
吸取教训,我还是写C代码吧:
int * move (int a[], int k, iny m) {
for (int j = 0, j <>
for (int i = 0; i <>
int tmp = a[i+1];
a[i+1] = a[i];
a[i] = tmp;
}
} //算了,不写返回语句了
}
嗯,两层循环,照书上的说法这个算法的时间复杂度应当是O(n2)——但是,那个m好像不足k吧?可以认为是O(n*m),但这样说是不严密的,因为O()仅处理上界情况。
好了,不多罗嗦了,下篇将揭晓真正有效率的算法——3个都是O(n)级的。

No comments: