进一步说明(ducktemple joyfire)收到了不少idea和反馈，谢谢大家的参与。有代表性的是ejqysl和sport2008的算法。 大多数人直接的想法，就是给数组里每个元素做记号，算出一个元素右移k以后的位置，交换；然后在从后面这个位置不断交换右移k。如果换了一圈又回到第一个已经换过的，则找到没有换过的元素，继续。 事实上，我自己最初的设计也是这样的。 但是这种方法会带来比较大空间复杂度，例如如果数组的n很大，甚至需要外排序，那么对应加上n个记号无疑比较浪费。而且每次移动之前都需要进行if判断的操作。 而ducktemple巧妙的借助了最大公约数来控制移动元素的过程，这样就不需要记录每个位置的元素是否移动过，自然也不需要不断的if比较操作。 一般条件下，此方法的时间效率和空间效率都比前面的方法好。当然，前面的方法也有适用情况，例如用汇编语言编程，没有求最大公约数的函数，相对而言比较语句的开销比较小。数组不太长（也许就是某个寄存器的各个位），效率就可能超过ducktemlpe的算法。 最后，有人使用了递归，似乎不如我们伪代码中的循环迭代好。 这道题表面上看起来很简单，但是在实际的代码书写中，我们两个还不断的找到可以继续优化的地方，例如用for语句替代原本的while语句，减少if判断等等。虽然我们为最终的程序的简练和效率自豪，但是还不敢说这就是最好的。这就是编程的乐趣所在吧。
|
Index中科院研究生考试的算法题(Mar. 26, 2003, by ducktemple joyfire) |