0

给定一个包含 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) 时间内完成。

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

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

4

5 回答 5

7

让我们看一下反转的最终数组：

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

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

于 2013-10-08T08:12:42.850 回答
5

试着想想这样的解决方案会是什么样子。如果您不能使用更多空间，则唯一可用的移动是交换元素。试着用一支笔来做，一个 2 个元素的数组，然后是一个 3。当你明白了它应该很容易。

事实上，使用交换需要一个变量，您可以使用 XOR 交换算法 ( http://en.wikipedia.org/wiki/XOR_swap_algorithm ) 来解决这个问题，但我认为这并不重要。

于 2013-10-08T07:34:12.240 回答
1

由于内存限制，这并非微不足道。首先将第一个元素移动到它的新位置，因为你不能存储太多元素 - 继续为你刚刚驱逐的元素寻找一个位置。

现在考虑一下通过次数与 GCD(n,m) 的关系，以及您的算法应该如何反映这一点 - 从 gcd 为 1 的常见情况开始（例如，如果在上面的示例中 m=3） - 一旦替换链将结束（您可以通过将当前索引与您开始使用的索引进行比较来检查），您将完成任务。但是，对于 GCD(m,n) > 1，您将只移动部分元素，并且您需要在您开始使用的最后一个元素之后立即使用该元素开始一个新链。

现在说服自己，无论阶段数如何，完成的移位总数都是 O(n)。

于 2013-10-08T08:01:18.117 回答
0

这是@MBo 向我暗示的一种恒定内存解决方案。除了数组空间和 m 之外，它还使用了 3 个额外变量：i、midpoint和endpoint. 它循环了 3 次，首先反转两个子数组，然后在最后一个循环中反转整个数组。它是 O(n/2 + m/2 + (nm) /2) 这只是 O(n) 因为 0 <= m < n 因为我m = m % n在开始时将任何给定的正 m 减少到一个数组范围内的索引。

交换还通过 2 项缓冲区（2 个元素的元组）发送值，但它仍然是交换的常量内存，所以没关系。

def rotateLeft(A, m):
    m %= len(A)
    # Reverse A[0..m-1]
    midpoint = m/2
    endpoint = m-1
    for i in xrange(midpoint):
        A[i], A[endpoint-i] = A[endpoint-i], A[i]
    # Reverse A[m..n-1]
    midpoint = m+(len(A)-m)/2
    endpoint = len(A)-1
    for i in xrange(m, midpoint):
        A[i], A[endpoint-(i-m)] = A[endpoint-(i-m)], A[i]
    # Reverses all elements of array in place
    midpoint = len(A)/2
    endpoint = len(A)-1
    for i in xrange(midpoint):
        A[i], A[endpoint-i] = A[endpoint-i], A[i]

它还允许负旋转（向右旋转），这在我看来非常简洁。这意味着rotateRight可以通过以下方式实现。

def rotateRight(A, m):
    rotateLeft(A, -m)

然后下面的代码将通过断言检查就好了。

A = [0, 1, 2, 3, 4, 5, 6]
B = A[:] # Make copy of A and assign it to B
rotateLeft(A, 4)
rotateRight(A, 4)
assert(A == B)
于 2013-10-08T09:36:14.870 回答
0

看下面的伪代码。对我来说似乎是正确的。

    function rotate(a[], a.length)
    {
     i = 0; 
     j = 0;
     k = 0; 
     temp = a[0];
     k = (i + a.length - 2 ) % a.length
     while (j < a.length){
     temp1 = a[k]
     a[k] =  temp;
     i = k;
     temp = temp1
     k = (i + a.length - 2 ) % a.length         
     j++
     }

     }
于 2013-10-08T09:02:04.787 回答