是否存在复杂度优于O(k*n)的数组内字符串k位旋转算法？

任务定义 #

字符串α的k位旋转指将前k个字符移至末尾得到字符串α[k:]α[:k]，例如将"abcdefghi"旋转4位得到"efghiabcd"。要求设计算法：输入为存储字符串的数组，在原数组内输出结果，且仅使用O(1)内存。

核心问题 #

是否存在时间复杂度优于O(k*n)的此类算法？

朴素实现代码 #

def move(arr, k):
    cur_k = 0
    while cur_k < k:
        i = 0
        while i < len(arr)-1:
            temp = arr[i]
            arr[i] = arr[i+1]
            arr[i+1] = temp
            i += 1
        cur_k += 1
    return arr

答案：存在，三次反转法实现O(n)时间复杂度 #

当然有更高效的算法——经典的三次反转法，可以做到O(n)时间复杂度，同时满足原地修改、O(1)额外内存的要求。

具体步骤如下：

• 反转数组的前k个元素
• 反转数组从第k个元素到末尾的部分
• 反转整个数组

举个实际例子，以数组['a','b','c','d','e','f','g','h','i']、k=4为例：

1. 反转前4个元素：得到['d','c','b','a','e','f','g','h','i']
2. 反转后5个元素：得到['d','c','b','a','i','h','g','f','e']
3. 反转整个数组：得到['e','f','g','h','i','a','b','c','d']，正好是目标旋转结果。

对应的Python实现代码：

def rotate(arr, k):
    n = len(arr)
    k = k % n  # 处理k大于数组长度的情况
    # 定义原地反转函数
    def reverse(left, right):
        while left < right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
    # 执行三次反转
    reverse(0, k-1)
    reverse(k, n-1)
    reverse(0, n-1)
    return arr

这个算法的时间复杂度是O(n)，因为三次反转操作总共遍历数组n次，相比朴素实现的O(k*n)效率提升明显，尤其是当k接近数组长度n时，优势会非常大。

内容的提问来源于stack exchange，提问作者some_guy256