阵列解释的循环旋转

Question

前提：我的问题不是Cyclic rotation in Python的重复。我不是在问如何解决问题，也不是问为什么我的解决方案不起作用，我已经解决了它，而且它起作用了。我的问题是关于我发现的同一问题的另一个特定解决方案，因为我想了解另一个解决方案背后的逻辑。在

我遇到了以下循环数组旋转问题（在源代码下方）：

• Cyclic rotation in Python
• https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/

An array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place). The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

我用下面的Python代码成功地解决了这个问题：

def solution(A , K):
    N = len(A)
    if N < 1 or N == K:
        return A
    K = K % N
    for x in range(K):
        tmp = A[N - 1]
        for i in range(N - 1, 0, -1):
            A[i] = A[i - 1]
        A[0] = tmp
    return A

然后，在下面的网站https://www.martinkysel.com/codility-cyclicrotation-solution/上，我找到了以下针对同一问题的奇特解决方案：

^{pr2}$

有人能给我解释一下这个特殊的解决方案是怎么工作的吗？（作者未在其网站上解释）

我的解决方案对于大的A和{}执行得不太好，其中K < N，例如：

^{3}$

因为对于K < N，我的代码具有O(N * K)的时间复杂度，其中N是数组的长度。 对于大的K和小的N（K > N），由于模运算K = K % N，我的解决方案表现得很好：

    A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    K = 999999999999999999999999
    expectedRes = [2, 3, 4, 5, 6, 7, 8, 9, 10, 1]
    res = solution(A, K) # 0.0048828125 ms, because K is torn down to 9 thanks to K = K % N

另一方面，另一个解决方案在所有情况下都能很好地执行，即使是在N > K并且复杂度为O(N)。在

这个解决方案背后的逻辑是什么？在

谢谢你的关注。在

Answer 1

让我先来谈谈K < N的基本情况，这个例子的思想是将数组分成两部分A和{}，A是第一个N-K元素数组，B是最后K个元素。该算法分别反转A和{}，最后对整个数组进行反转（两部分分别反转）。要使用K > N来管理这种情况，请认为，每次您将数组反转N次，您就可以再次获得原始数组，这样我们就可以使用module运算符来查找数组的拆分位置（只反转真正有用的时间，避免无用的移位）。在

图形示例

一个循序渐进的图形示例有助于更好地理解概念。请注意

• 粗体线表示数组的拆分点（K = 3在本例中）
• 红色数组表示输入和预期输出。在

起始时间：

看，我们在最终输出前面想要的是最后3个字母的倒转，现在让它在适当的地方反转（算法的第一个反转）：

现在反转第一个N-K元素（算法的第二个反转）：

我们已经有了解决方案，但在相反的方向上，我们可以反向求解整个数组（算法的第三个和最后一个反转）：

这里的最终输出，原始数组循环旋转K=3。在

代码示例

让我们用python代码给出另一个循序渐进的例子，从：

A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
K = 22
N = len(A)

我们发现分裂指数：

^{pr2}$

因为在这种情况下，前20个移位将是无用的，现在我们反转原始数组的最后K（2）个元素：

^{3}$

如您所见，9和10已经移位，现在我们反转第一个N-K元素：

reverse(A, 0, N-K-1)
# [8, 7, 6, 5, 4, 3, 2, 1, 10, 9]

最后，我们反转整个阵列：

reverse(A, 0, N-1)
# [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]

注意，反转数组的时间复杂度为O（N）。在