python - 数组解释的循环旋转

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/ ，我发现了以下针对同一问题的奇特解决方案:

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和 B , A是第一个 N-K 个元素数组，B最后 K 个元素。算法反转 A和 B分别并最终反转整个数组(两部分分别反转)。使用 K > N 管理案例，认为每次将数组反转 N 次都会再次获得原始数组，因此我们可以使用模块运算符找到拆分数组的位置(仅反转真正有用的次数，避免无用的移位)。

图形示例

图形化的分步示例有助于更好地理解概念。注意

• 粗线表示数组的 split 点(本例中为K = 3)；
• 红色数组表示输入和预期输出。

开始于:

看看我们想要在最终输出前面的是最后 3 个字母反转，现在让它反转到位(算法的第一次反转):

现在反转前 N-K 个元素(算法的第二个反转):

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

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

代码示例

让我们再给出另一个使用 python 代码的分步示例，从:

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

我们找到 split 指数:

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 已经移位，现在我们反转前 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)。