算法题：把列表右侧 k 位数依次移动到左侧

摄影：产品经理~产品经理送的礼物~

给定一个非空列表和一个非负整数 k，把列表右侧的 k 位依次移动到左侧。例如：[1, 2, 3, 4, 5, 6]，n 为3，则移动以后，变为：[4, 5, 6, 1, 2, 3]。

这道题看起来非常简单，几行代码就能解决：

def shift(target_list, k):
    for i in range(k):
        target_list.insert(0, target_list.pop())

其中，列表的.pop()方法每次可以从列表中返回并删除最右侧的一个元素。再使用.insert()把弹出的这个数插入到列表的最左侧。

但这样做有一个问题——虽然.pop()的时间复杂度为 O(1)，但是.insert()的时间复杂度为 O(n)。也就是说，当我在列表最左侧插入一个元素时，列表里面每一个元素都要向右移动 1 位。如果我们要把列表里面右侧 k 个数依次移动到列表左侧，时间复杂度就是O(kn)。

那么有没有O(n)时间复杂度的方法呢？当然是有了。

1. 首先把列表翻转，例如[1, 2, 3, 4, 5, 6]变成[6, 5, 4, 3, 2, 1]。翻转列表的时间复杂度为O(n/2)。
2. 把前k个数翻转：[4, 5, 6, 3, 2, 1]。时间复杂度为O(k/2)
3. 把第剩下的 n - k个数翻转：[4, 5, 6, 1, 2, 3]。时间复杂度为O((n-k)/2)

整体的时间复杂度为 O(n)。

对应的 Python 代码如下：

def swap(target_list, start, end):
    while start < end:
        target_list[start], target_list[end] = target_list[end], target_list[start]
        start += 1
        end -= 1
def shift(target_list, k):
    length = len(target_list)
    k = k % length
    swap(target_list, 0, length - 1)
    swap(target_list, 0, k - 1)
    swap(target_list, k, length - 1)

如果 k 大于列表长度，相当于转了一圈又从头开始，所以真正需要移动的举例为列表长度对 k 求余数。

运行效果如下图所示：