用于 M 位置的圆形移位 N 大小数组的最快算法 [英] Fastest algorithm for circle shift N sized array for M position

问题描述

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

What is the fastest algorithm for circle shifting array for M positions?
For example, [3 4 5 2 3 1 4] shift M = 2 positions should be [1 4 3 4 5 2 3].

非常感谢.

推荐答案

如果您想要 O(n) 时间并且不使用额外的内存(因为指定了数组)，请使用 Jon Bentley 的书Programming Pearls 2nd Edition"中的算法".它将所有元素交换两次.不像使用链表那么快，但使用更少的内存并且概念上很简单.

If you want O(n) time and no extra memory usage (since array was specified), use the algorithm from Jon Bentley's book, "Programming Pearls 2nd Edition". It swaps all the elements twice. Not as fast as using linked lists but uses less memory and is conceptually simple.

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，包括在内.

reverseArray( anArray, startIndex, endIndex ) reverses the order of elements from startIndex to endIndex, inclusive.

这篇关于用于 M 位置的圆形移位 N 大小数组的最快算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！