0

我一直在解决https://www.lintcode.com/上的问题，在做其中一个问题时遇到了问题。这个问题需要我写一个有两个参数的函数。一个数字列表和一个目标数字。您必须从列表中获取目标的所有实例并将它们移动到原始列表的前面，并且该函数不能有返回值。列表的长度在 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

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

4

2 回答 2

2

这是一个简单且相对有效的实现：

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

它创建一个新列表，其中n包含前面的目标值，并附加所有其他非目标值。nums由于表达式，输入列表发生了变异nums[:] = ...。

该解决方案以线性时间运行，而不是之前提出的实现（以二次时间运行）。实际上，在 CPythoninsert中以线性时间运行。

于 2021-08-14T23:19:24.613 回答
-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))
于 2021-08-14T23:01:30.963 回答