python - 使用常量内存旋转 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)

你看到了什么有趣的东西吗？