algorithm - 用于M位置的N大小数组的圆移最快算法

什么是M个位置的圆移阵列最快的算法？
例如，[3 4 5 2 3 1 4] shift M = 2个位置应为[1 4 3 4 5 2 3]。

非常感谢。

最佳答案

如果需要O(n)时间并且不占用额外的内存(因为已指定数组)，请使用Jon Bentley的书“Programming Pearls 2nd Edition”中的算法。它将所有元素交换两次。速度不如使用链表快，但占用的内存更少，并且在概念上很简单。

shiftArray( theArray, M ):
    size = len( theArray )
    assert( size > M )
    reverseArray( theArray, 0, size - 1 )
    reverseArray( theArray, 0, M - 1 )
    reverseArray( theArray, M, size - 1 )

reverseArray(anArray，startIndex，endIndex)将元素的顺序从startIndex转换为endIndex(包括端点)。