c++ - 在 2D Vector 字符串中查找重复项

Question

我想知道 2d Vector 表是否有重复项。我可以看到很多使用独特的 STL 算法删除重复项的程序。对于 100,000 条记录，这是查找“是否重复”的最佳方法。

Answer 1

我会对这张表进行排序，然后使用二分法搜索重复项。这将是 O(n^2 log n) 复杂度。与这样的排序进行比较:

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

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