Python代码优化问题（Lintcode问题1886移动目标）

Question

我一直在研究 https://www.lintcode.com/ 的问题，并且在做其中一个问题时遇到了运行问题。这个问题要求我写一个有两个参数的函数。 nums 列表和目标 num。您必须从列表中取出目标的所有实例并将它们移动到原始列表的前面，并且该函数不能具有 return 值。列表的长度在 1 到 1000000 之间。您还必须在大约 400 毫秒的时间限制内完成。我可以解决问题，我无法通过列表长度为 1000000 的最后一个测试用例。有谁知道如何让我的代码更快？

对于仍然不清楚的人的原始问题描述：

当前代码：

def MoveTarget(nums, target):
    if len(set(nums)) == 1:
        return nums
    index = [i for i in range(len(nums)) if nums[i] == target]
    for i in index:
        nums.insert(0, nums.pop(i))

如果你这样做就有效：

def MoveTarget(nums, target): 
    count = 0
    left, right = len(nums) - 1, len(nums) - 1
    
    while left >= 0:
        if nums[left] != target:
            nums[right] = nums[left]
            right -= 1
        else:
            count += 1
        left -= 1
        
    for i in range(count):
        nums[i] = target

但我想知道是否还有另一种不那么复杂的方法。

Answer 1

您的代码使用了 2 个循环。其中一个：

index = [i for i in range(len(nums)) if nums[i] == target]

还有一个在：

for i in index:
    nums.insert(0, nums.pop(i))

相反，您可以将找到目标并将其移动到数组的前面与一个循环结合起来，这将大大减少执行时间：

def MoveTarget(nums, target):
    if len(set(nums)) == 1:
        return nums
    for num in nums:
        if num == target:
            nums.insert(0, nums.pop(num))

Answer 2

下面是一个简单且相对高效的实现：

def MoveTarget(nums, target):
    n = nums.count(target)
    nums[:] = [target] * n + [e for e in nums if e != target]

它创建一个新列表，其中 n 目标值位于前面，并附加所有其他非目标值。由于表达式 nums[:] = ....

，输入列表 nums 发生了变异

解决方案运行 线性时间 与之前提出的实施方案（运行ning 在二次时间）相反。实际上，CPython 中的insert runs in linear time。

Python代码优化问题（Lintcode问题1886移动目标）

Python Code Optimization Problem (Lintcode Problem 1886 Moving Targets)

python

optimization

list

time-limiting