使用常量存储器旋转m个位置左侧的n个元素的一维数组？

Question

给定n个元素的一维数组,以及如何有效地旋转数组,使数组的元素向左移动m个位置？是否可以仅使用常数O(1)内存以O(n)时间复杂度执行此操作？

例如,如果n = 8并且你的数组是,[0, 1, 2, 3, 4, 5, 6, 7]并且你将它向左旋转m = 2,那么你就得到了[2, 3, 4, 5, 6, 7, 0, 1].

这是我实现的Python中的天真解决方案,它使用O(n)时间和O(n)内存和临时数组.

def rotateLeft(A, m):
    temp = [None]*len(A)
    for i in xrange(len(temp)):
        temp[i] = A[(i + m) % len(A)]
    for i in xrange(len(A)):
        A[i] = temp[i]

我怎么能更有效地做到这一点？我被告知这可以通过恒定的内存量来完成,并且仍然在O(n)时间内.

任何语言的解决方案都可以,任何建议都非常受欢迎.

编辑:我不是在寻找图书馆解决方案.此外,该数组不是链表/双端队列.没有头/尾/下一个/前一个元素的概念.

Answer 1

让我们看一下反向的最终数组:

[1, 0,    7, 6, 5, 4, 3, 2]    (spacing mine)

你看到有趣的东西吗？

Answer 2

试着想一下像这样的解决方案会是什么样子.如果您不能使用更多空间,唯一可用的移动是交换元素.尝试使用笔,2个元素数组,然后是3个.在得到这个想法后,它应该很容易.

实际上,使用swap需要一个变量,你可以使用XOR交换算法(http://en.wikipedia.org/wiki/XOR_swap_algorithm)解决这个问题,但我不认为这非常重要.