Python中数组旋转的切片逗号交换操作空间复杂度是多少？

你编写的切片交换代码如下：

nums[n-k:],nums[:n-k] = nums[:n-k], nums[n-k:]

上述代码的空间复杂度为O(n)，不属于O(1)的原地操作，具体原因如下：

• Python的列表切片操作nums[left:right]会生成对应子列表的全新副本，占用的内存空间和切片长度成正比。你代码中的nums[:n-k]和nums[n-k:]两个切片总长度为n，会先生成两个总大小为n的临时列表副本，再将这两个副本赋值回原列表的对应位置，因此额外空间开销为O(n)。
• 普通a,b = b,a交换普通变量时仅需要临时存储两个变量的引用，开销为O(1)，但切片交换的本质是批量拷贝数据，Python没有针对这种场景做特殊优化，不会跳过生成临时副本的步骤。

如果要实现真正O(1)空间的原地数组旋转，可以用经典的三次翻转法，示例实现如下：

def rotate(nums, k):
    n = len(nums)
    k = k % n
    # 定义翻转指定区间的辅助函数
    def reverse_sub(start, end):
        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1
    # 1. 翻转整个数组
    reverse_sub(0, n-1)
    # 2. 翻转前k个元素
    reverse_sub(0, k-1)
    # 3. 翻转后n-k个元素
    reverse_sub(k, n-1)

该实现仅用到常数个临时变量，没有额外的线性空间开销，符合O(1)空间复杂度的要求。

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