我有一个家庭作业问题来编写一个函数，该函数是类bagOfWords的一部分，用于从未排序的列表中删除值的实例。 我们可以使用的列表操作不包括 remove()。 我们只需要 O(n) 复杂度，而朴素算法表现不佳。
我尝试了一个幼稚的算法。 这是一个太复杂的算法。 它使用 list.pop(index)，它本身具有 O(n) 复杂性，并且有两个循环。 由于我们不允许使用 list.remove()，并且因为列表理解具有相同的复杂性，但语法更简洁，我正在尝试找到更好的实现。
我想也许解决方案是一种快速排序算法，因为如果我首先对列表进行排序，我可能能够以 O(n) 的复杂性做到这一点。 但是，如何在没有pop(index)复杂性的情况下删除此项目呢？ 现在我想知道通过 KMP 算法搜索模式是否是解决方案，还是哈希。
def remove(self, item):
"""Remove all copies of item from the bag.
Do nothing if the item doesn't occur in the bag.
"""
index = 0
while index < len(self.items):
if self.items[index] == item:
self.items.pop(index)
else:
index += 1
复杂性是二次的。 但是，我想要一个 O(n) 的复杂性
编辑：澄清一下，我们实际上只能修改现有列表。
编辑：最简单的(可以说只是"正确")的方法是使用列表理解：
self.items = [x for x in self.items if x != item]
它是 O(n)，它比以下选项更快。它也是迄今为止最"蟒蛇"的。
但是，它确实会创建列表的新副本。如果您实际上只能修改现有列表，这是我的原始答案：
这是一个"就地"O(n)算法，它使用两个指针折叠列表，删除不需要的元素：
ixDst = 0 for ixSrc in range(0, len(items)): if items[ixSrc] != item: items[ixDst] = items[ixSrc] ixDst += 1 del items[ixDst:](看到它运行在这里)
唯一有问题的部分是用
del缩小列表大小。我相信这是就位的，"应该"是 O(1)，因为我们要删除的切片位于列表的末尾。
此外，@chepner在评论中提出了一个更pythonic的就地答案(并且更快)：
self.items[:] = (x for x in self.items if x != item)
感谢@juanpa.arrivillaga和@chepner的讨论。
如果你列出的元素是相对较小的整数，或者可以这样表示，你可以在O(max(maxValue， n))中进行排序。
另一种方法是为列表中的每个元素提供指向上一个和下一个元素的指针。这样，您可以删除 O(1) 中的一个元素。但是，这使得按索引获取项目的操作在 O(n) 时间内运行。
此外，如果项目的顺序无关紧要，您可以存储像(item, count)这样的对，其中count是item出现的次数，那么对于给定的item，您只需删除一个这样的对并具有所需的复杂性。
希望对您有所帮助！
如果需要它来执行就地删除，则可以将项目移到已删除的项目上，并在最后的一个操作中截断列表：
index = 0
for value in self.items:
if value != item :
self.items[index] = value
index += 1
del self.items[index:]
如果你有能力创建一个新列表(没有列表理解)，你可以这样做：
cleanedItems = []
for value in items:
if value != item: cleanedItems.append(value)
self.items = cleanedItems