检查向量中的重复项

Question

可能重复:
确定无序向量<T>是否具有所有唯一元素

我必须检查一个矢量的重复.解决这个问题的最佳方法是什么:

我拿第一个元素,将它与向量中的所有其他元素进行比较.然后采取下一个元素并执行相同的操作,依此类推.

这是最好的方法,还是有更有效的方法来检查重复？

Answer 1

如果您的向量是STL容器,则解决方案很简单:

• 第一种
• 然后'独特'

例如:

std::sort(myvec.begin(), myvec.end());
std::erase(std::unique(myvec.begin(), myvec.end()), myvec.end());

请注意,std :: unique实际上不会删除重复项,而是将它们移动到容器的末尾并将迭代器返回到第一个副本.因此,根据情况,您可能希望使用std :: remove来删除容器的尾部,或者使用std :: copy仅将非重复项复制到另一个容器.

Answer 2

使用哈希表,在其中插入每个元素.在插入元素之前,请检查它是否已存在.如果是,你自己就是副本.这是O(n) 平均水平,但最糟糕的情况与您当前的方法一样糟糕.

或者,在最坏的情况下,您可以使用一组来执行相同的操作O(n log n).这与排序解决方案一样好,除了它不会改变元素的顺序(因为你创建了一个集合后使用了更多的内存).

另一种方法是将矢量复制到另一个矢量,对其进行排序并检查那里的相邻元素.我不确定这是否比设置解决方案更快,但我认为排序比一组使用的平衡搜索树增加了更少的开销,所以它在实践中应该更快.

当然,如果你不关心保持元素的原始顺序,只需对初始向量进行排序.