LeetCode Rotate Array问题Python解法超时优化咨询

问题分析 #

你的代码触发超时的核心原因是while循环里的nums.append(nums[0])和del nums[0]操作：Python列表属于动态数组结构，删除头部元素需要将后续所有元素向前移位，单次操作时间复杂度为O(n)。当k达到5万+、数组长度为10万时，总时间复杂度会飙升至O(k*n)，运算量远超时间限制。

另外代码未处理k >= len(nums)的情况，若k远大于数组长度，会执行大量无意义的重复循环，进一步浪费性能。

优化方案 #

方案1：三次反转法（时间O(n)，空间O(1)，纯原地修改） #

这是旋转数组问题的经典最优解法，所有操作均在原数组上完成，无额外空间开销：

1. 反转整个数组
2. 反转前k个元素
3. 反转剩余的n-k个元素

关键前提：先对k取模，避免k大于数组长度时做重复操作（比如数组长度10万，k=15万等价于k=5万）。

优化后的代码：

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        
        # 反转整个数组
        nums.reverse()
        # 反转前k个元素
        nums[:k] = reversed(nums[:k])
        # 反转剩余元素
        nums[k:] = reversed(nums[k:])

如果想完全手动实现反转逻辑（避免切片生成临时列表的微小开销），可以写成：

class Solution(object):
    def rotate(self, nums, k):
        def reverse(lst, start, end):
            while start < end:
                lst[start], lst[end] = lst[end], lst[start]
                start += 1
                end -= 1
        
        n = len(nums)
        k = k % n
        reverse(nums, 0, n-1)
        reverse(nums, 0, k-1)
        reverse(nums, k, n-1)

方案2：切片赋值（简洁高效，原地修改） #

利用Python切片特性直接重组数组，注意必须用nums[:] = ...而非nums = ...——后者仅改变变量引用，不会修改原数组：

class Solution(object):
    def rotate(self, nums, k):
        n = len(nums)
        k = k % n
        nums[:] = nums[-k:] + nums[:-k]

该方法时间复杂度O(n)，空间复杂度O(n)（切片会生成临时列表），但代码极简，LeetCode测试用例通常不会限制这种级别的空间开销。

原代码低效根源复盘 #

• 单次del nums[0]是O(n)操作，k次循环累积为O(k*n)，当k和n均为10万级别时，运算量达到1e10，远超时间阈值。
• 未对k取模，若k远大于数组长度，会执行大量无效循环。

内容的提问来源于stack exchange，提问作者Mikhail Sh.