在2D中查找重复向量字符串

Question

我想查找是否存在重复的2d向量表。我可以看到很多使用独特的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)。