数组循环移位

设计一个算法，把一个含有N个元素的数组循环右移k位，要求时间复杂度为O(N)，且只允许使用两个附加变量。

解法 1

不符合题意得解法1：

一个简单的解法就是循环k次每次将数组内的元素右移一位。

def RightShif(arr,n,k):
    while k>0:
        k -= 1
        t = arr[n-1]
        for i in range(n-1,0,-1):
            arr[i] = arr[i-1]
        arr[0] = t
arr = ['a','b','c','d',1,2,3,4]
n = len(arr)
k = 4
RightShif(arr,n,k)
print(arr)

因为该算法时间复杂度为O(K*N)，不符合题目要求因此需要继续寻找符合要求的算法。

解法 2

由于解法1中的k有可能大于n，当k远大于n时，右移k个单位的情形，和右移k‘ = k%n个单位的时间复杂度一样。优化后的代码如下：

def RightShif(arr,n,k):
    k = k % n
    while k>0:
        k -= 1
        t = arr[n-1]
        for i in range(n-1,0,-1):
            arr[i] = arr[i-1]
        arr[0] = t
arr = ['a','b','c','d',1,2,3,4]
n = len(arr)
k = 2*n+4
RightShif(arr,n,k)
print(arr)

优化后的代码时间复杂度为O(N*(k%N))，该时间复杂度仍不满足题目要求。

解法 3

解法3的话，老实说我想不出来。太具有规律性了。变化过程如下：

1. 逆序排列前面n-k位。
2. 逆序排列后k位
3. 前部逆序

1，2过程可以互换。时间复杂度为O(N).满足题目要求。

def Reverse(arr,l,r):
    while l < r:
        arr[l], arr[r] = arr[r], arr[l]
        l += 1
        r -= 1
def RightShif(arr,n,k):
    k %= n
    Reverse(arr,0,n-k-1)
    Reverse(arr,n-k,n-1)
    Reverse(arr,0,n-1)
arr = ['a','b','c','d',1,2,3,4]
n = len(arr)
k = 2*n+4
RightShif(arr,n,k)
print(arr)