检查向量中的重复项 [英] Checking for duplicates in a vector

问题描述

可能重复：

确定无序向量< T>具有所有唯一元素

我必须检查一个向量是否重复。什么是最好的方法来处理这个：

I have to check a vector for duplicates. What is the best way to approach this:

我采取第一个元素，与矢量中的所有其他元素进行比较。

I take the first element, compare it against all other elements in the vector. Then take the next element and do the same and so on.

这是最好的方法吗，还是有更有效的方法来检查dups？ / p>

Is this the best way to do it, or is there a more efficient way to check for dups?

推荐答案

使用哈希表，其中插入每个元素。在插入元素之前，请检查它是否已存在。如果是，你自己有一个重复。这是 O（n） 平均，但最坏的情况是同样糟糕的当前方法。

Use a hash table in which you insert each element. Before you insert an element, check if it's already there. If it is, you have yourself a duplicate. This is O(n) on average, but the worst case is just as bad as your current method.

或者，您可以使用设置执行最坏的情况是 O（n log n）这与排序解决方案一样好，除了它不改变元素的顺序（尽管自创建集合以来使用更多的内存）。

Alternatively, you can use a set to do the same thing in O(n log n) worst case. This is as good as the sorting solution, except it doesn't change the order of the elements (uses more memory though since you create a set).

另一种方法是将您的向量复制到另一个向量，排序，并检查相邻的元素。我不知道这是否比设置的解决方案更快，但我认为排序比一组使用的平衡搜索树增加更少的开销，因此它应该更快在实践中。

Another way is to copy your vector to another vector, sort that and check the adjacent elements there. I'm not sure if this is faster than the set solution, but I think sorting adds less overhead than the balanced search trees a set uses so it should be faster in practice.

当然，如果你不在乎保持元素的原始顺序，只需排序初始向量。

Of course, if you don't care about keeping the original order of the elements, just sort the initial vector.

这篇关于检查向量中的重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！