小编典典

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

algorithm

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

非常感谢。


阅读 211

收藏
2020-07-28

共1个答案

小编典典

如果需要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(包括端点)。

2020-07-28