在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)。