数组循环旋转解释

Question

前提：我的问题不是Python 中的循环旋转的重复。我不是在问如何解决问题或为什么我的解决方案不起作用，我已经解决了它并且它有效。我的问题是关于我发现的同一问题的另一个特定解决方案，因为我想了解其他解决方案背后的逻辑。

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

• Python中的循环旋转
• https://app.codility.com/programmers/lessons/2-arrays/circular_rotation/

给出一个由 N 个整数组成的数组 A。数组的旋转意味着每个元素右移一个索引，并将数组的最后一个元素移动到第一位。例如，数组 A = [3, 8, 9, 7, 6] 的旋转为 [6, 3, 8, 9, 7]（元素右移一个索引，6 移至第一位）。目标是旋转阵列AK次；即A的每个元素都会右移K次。

我设法用以下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-circularrotation-solution/上，我找到了针对同一问题的以下奇特解决方案：

def reverse(arr, i, j):
    for idx in xrange((j - i + 1) / 2):
        arr[i+idx], arr[j-idx] = arr[j-idx], arr[i+idx]

def solution(A, K):
    l = len(A)
    if l == 0:
        return []

    K = K%l

    reverse(A, l - K, l -1)
    reverse(A, 0, l - K -1)
    reverse(A, 0, l - 1)

    return A

有人可以解释一下这个特定的解决方案是如何工作的吗？（作者在他的网站上没有解释）

A我的解决方案对于大型和K，其中表现不佳K < N，例如：

    A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] * 1000
    K = 1000
    expectedResult = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] * 1000
    res = solution(A, K) # 1455.05908203125 ms = almost 1.4 seconds

因为对于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并且是第一个 NK 元素数组和最后 K 个元素。该算法分别反转和最后反转整个数组（两部分分别反转）。为了使用 来管理这种情况，请认为每次反转数组 N 次时，您都会再次获得原始数组，因此我们可以使用模运算符来查找拆分数组的位置（仅反转真正有用的时间，避免无用的移位）。BABABK > N

图解示例

图形化的分步示例可以帮助更好地理解这个概念。注意

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

从...开始：

看看我们在最终输出前面想要的将是最后 3 个字母反转，现在让其反转（算法的第一个反转）：

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

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

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

代码示例

让我们用 python 代码给出另一个分步示例，从以下位置开始：

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

我们找到分裂索引：

K = K%N
#2

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

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

正如你所看到的 9 和 10 已经移位，现在我们反转第一个 NK 元素：

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)。