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

如果列表中的元素是相对较小的整数或可以表示为这样，则可以在 O(max(maxValue, n)) 中进行排序。

另一种方法是为列表中的每个元素提供指向上一个和下一个元素的指针。这样你就可以在 O(1) 时间内删除一个元素。然而，这使得通过索引获取项目的操作在 O(n) 时间内运行。

此外，如果项目的顺序并不重要，您可以存储对，例如(item, count)出现的count次数item，那么您只需删除给定的一个这样的对item，并具有所需的复杂性。

希望能帮助到你！