数组向右旋转k步：如何实现O(n)时间与O(1)空间复杂度？

当然存在这种方案，核心思路是三次原地反转，完全满足O(n)时间复杂度和O(1)空间复杂度的要求，具体步骤如下：

第一步：处理k的有效值 #

当k大于数组长度n时，旋转n步等于没旋转，所以先计算 k = k % n，避免做无用功。比如数组长度是7，k=10的话，实际等效于k=3。

第二步：三次反转操作 #

以示例 nums = [1,2,3,4,5,6,7]，k=3为例：

1. 反转整个数组：把数组从首尾开始两两交换，得到 [7,6,5,4,3,2,1]
2. 反转前k个元素：对前3个元素 [7,6,5] 反转，得到 [5,6,7,4,3,2,1]
3. 反转剩余的n-k个元素：对后面4个元素 [4,3,2,1] 反转，得到最终结果 [5,6,7,1,2,3,4]

代码实现（Python原地操作） #

def rotate(nums, k):
    n = len(nums)
    k = k % n
    
    # 定义原地反转函数
    def reverse(start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
    
    reverse(0, n-1)
    reverse(0, k-1)
    reverse(k, n-1)

复杂度说明 #

• 时间复杂度：三次反转的总操作次数是n + k + (n-k) = 2n，属于O(n)级别
• 空间复杂度：全程只用到了几个指针变量，没有额外开辟数组，是O(1)

内容的提问来源于stack exchange，提问作者Альберт Александров