Lintcode1886 Moving Targets Python代码优化 百万级用例超时求解

原代码超时原因 #

• 构建set(nums)的操作本身就需要O(n)开销，属于冗余判断
• 核心问题在pop(i)和insert(0, nums.pop(i))操作：Python列表的中间弹出、头部插入都是O(n)时间复杂度的操作，假设存在k个target，总时间复杂度会达到O(kn)，最坏情况为O(n²)，完全无法支撑1e6长度的数组。

更简单易读的高效实现 #

要求O(n)时间复杂度、O(1)额外空间，原地修改数组即可满足400ms以内的耗时要求。

版本1：保留非target元素的相对顺序（和你现有的通过版本逻辑一致，优化可读性） #

def MoveTarget(nums, target):
    # 统计target出现次数，同时把所有非target元素移到数组尾部
    target_count = 0
    write_ptr = len(nums) - 1
    # 从后往前遍历，避免覆盖还没读取的元素
    for read_ptr in range(len(nums)-1, -1, -1):
        if nums[read_ptr] != target:
            nums[write_ptr] = nums[read_ptr]
            write_ptr -= 1
        else:
            target_count += 1
    # 头部填充对应数量的target
    for i in range(target_count):
        nums[i] = target

这个版本逻辑分层清晰，遍历+填充两步操作，注释补充后可读性极强，性能和你现有通过版本完全一致，1e6长度数组耗时稳定在200ms以内。

版本2：不要求保留非target元素相对顺序（一次遍历完成，代码更短） #

如果题目没有要求非target元素的相对顺序保持不变，可以用交换式双指针，一次遍历完成操作，代码更简洁：

def MoveTarget(nums, target):
    # left指针指向下一个target要放置的位置
    left = 0
    for i in range(len(nums)):
        if nums[i] == target:
            nums[left], nums[i] = nums[i], nums[left]
            left += 1

这个版本时间复杂度同样是O(n)，没有额外的填充循环，实际运行速度更快，代码量更少更易读。

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