python - O(n) 复杂度算法，无需 remove() 方法即可从未排序的列表中删除值的实例

Question

我有一个家庭作业问题是编写一个函数，该函数是类 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)

编辑:澄清一下，我们实际上只能修改现有列表。

Answer 1

编辑:最简单(也可以说是“正确”)的方法是使用列表理解:

self.items = [x for x in self.items if x != item]

它的复杂度为 O(n)，并且比以下选项更快。它也是迄今为止最“pythonic”的。

---

但是，它确实创建了列表的新副本。如果您实际上不得不修改现有列表，这是我的原始答案:

Here's an "in-place" O(n) algorithm that uses two pointers to collapse the list down, removing the unwanted elements:

ixDst = 0
for ixSrc in range(0, len(items)):
  if items[ixSrc] != item:
    items[ixDst] = items[ixSrc]
    ixDst += 1
del items[ixDst:]

(See it run here)

The only questionable part is resizing the list down with del. I believe that's in-place and "should" be O(1), since the slice we're removing is at the end of the list.

此外，@chepner 在评论中建议了一个更 pythonic 的就地答案(并且更快一点):

self.items[:] = (x for x in self.items if x != item)

感谢@juanpa.arrivillaga 和@chepner 的讨论。