Python代码优化问题(Lintcode问题1886移动目标)
提问于 2021-08-14 14:41:28
我一直在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但我想知道是否还有另一种不那么复杂的方法。
回答 2
Stack Overflow用户
回答已采纳
发布于 2021-08-14 15:19:24
下面是一个简单和相对有效的实现：
def MoveTarget(nums, target):
n = nums.count(target)
nums[:] = [target] * n + [e for e in nums if e != target]它使用前面的n目标值创建一个新列表，并追加所有其他非目标值。由于表达式nums，输入列表nums[:] = ...会发生变异。
该解决方案在线性时间中运行，而不是以前建议的实现(在二次时间内运行)。的确，insert runs in linear time in CPython。
Stack Overflow用户
发布于 2021-08-14 15:01:30
您的代码使用两个循环。其中一人：
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))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/68787510
复制
腾讯云开发者
