September 25, 2006

关于数组左移问题的一个新想法

本来要继续写数组左旋下篇(上篇在此)的,今天在课堂上忽然想到一个新办法 :既然可以证明每一个元素的新位置是((k - m) + i ) % k,我何不再仔细分析一下数组的直接移动过程?
对于k = 5,m = 2:
#注:蓝色线表示元素向右的移动过程,绿色表示向左的移动过程。
不难发现,向右移动时,元素下标从 i 改变到 i + k - m,而向左移动时是 i - m(显然)。
再验证一下吧:为什么这个用了两次直接移动?似乎 k % m == 0 时就需要做 m 次,否则要做1次。
没错。但算法写得可不能如此精神分裂——这个现象肯定有更深层次的原因。
再演算一下,终于弄明白了:每种方向的移动其实是个循环过程,每次寻找 k 中可存放元素的下标位置;当期望的下标大于 k 时,元素就要向反方向找位置了。
理清了算法的操作过程,大致的想法也就成型了:有一个分两种情况找位置的递归函数,当 k % m == 0 时循环调用它 m 次,当 k % m == 1时一次即可。比如:
显然这个算法只进行了 k 次赋值(计算次数可以忽略不计),效率应当非常高。
具体代码等我写完《谈谈数组左旋问题(下)》再说吧!

No comments: