c++ - 在二维向量字符串中查找重复项

Question

我想找出二维向量表是否重复。我可以看到很多使用独特的 STL 算法删除重复项的程序。对于 100,000 条记录，哪种方法是查找“是否重复”的最佳方法。

Answer 1

我会对这个表进行排序，然后用二进制搜索来搜索 dups。这将是O(n^2 log n)复杂的。比较排序与这样的东西：

p1.x < p2.x   ||  (p1.x==p2.x  &&  p1.y < p2.y) 

大多数人会告诉你为此使用哈希表，但O(n^2)在最坏的情况下，哈希表有构建时间。所以总复杂度将是O(n^3)。