M个位置的圆移阵列最快的算法是什么? 例如,[3 4 5 2 3 1 4]移位M = 2位置应为[1 4 3 4 5 2 3]。
[3 4 5 2 3 1 4]
[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(包括端点)。