Python中pop与insert操作性能瓶颈分析及LeetCode 189. Rotate Array问题代码优化咨询

Let's break down why your current code is underperforming, then walk through better approaches that meet the problem's in-place modification requirement.

Why Your Code Is Slow #

You assumed your loop runs in O(k) time, but the hidden cost of the insert operation changes everything:

• nums.pop() from the end of a Python list is O(1) — it just adjusts the list's internal pointer without moving other elements.
• However, nums.insert(0, ...) is an O(n) operation (where n is the length of the list). Inserting at the start forces every existing element to shift one position right to make space, which gets very expensive as the array grows.

This makes your total time complexity O(k * n). For large arrays (like 100,000 elements) and k close to n, this becomes O(n²) time — way too slow for big test cases, which explains the poor performance you're seeing.

Better In-Place Rotation Approaches #

1. Three-Reverse Method (Optimal O(n) Time, O(1) Space) #

This is the standard optimal solution for in-place rotation. The logic is simple:

• Reverse the entire array.
• Reverse the first k elements.
• Reverse the remaining n - k elements.

First, we handle cases where k >= n by computing k = k % n — rotating n times brings the array back to its original state, so we only need the remainder.

Here's the code:

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n  # Eliminate redundant rotations
        
        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)

Each reverse operation runs in O(m) time (where m is the length of the subarray), so total time is O(n) with no extra space beyond a few variables.

2. Pythonic Slice Assignment (O(n) Time, O(n) Space) #

While this uses O(n) space (slicing creates new lists), it's concise and performs well for most scenarios. The key is using nums[:] to modify the original list in-place instead of creating a new one:

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k = k % n
        nums[:] = nums[-k:] + nums[:-k]

nums[-k:] grabs the last k elements, nums[:-k] grabs the first n - k elements, and concatenating them assigns directly to the original list.

Key Takeaways #

• Always account for hidden costs of list operations: inserting at the start/middle of a dynamic array is expensive, while appending/popping from the end is cheap.
• For in-place problems, avoid solutions that require shifting elements multiple times (like your original loop).
• Never forget to handle k >= n with modulo arithmetic — rotating more times than the array length is redundant.

内容的提问来源于stack exchange，提问作者Albert G Lieu