在二維矢量中找到唯一對的最快方法

Question

我正在尋找一種高效且快速的算法來在二維矢量中查找唯一對。例如： vec = [[1 5] [2 2] [1 5] [3 1] [6 3] [2 2]] 我想生成下面只有唯一對的2d向量。 vec = [[1 5] [2 2] [3 1] [6 3]]

演示與僞代碼（或任何C類似的語法）將深受讚賞。

非常感謝提前

Answer 1

我不知道如何快速算法你在尋找，但NlogN + N算法思想

//create an extra vector, we call it sol 
vec = [[1 5], [2 2], [1 5], [3 1], [6 3], [2 2]] 
sort(vec)  
i = 0 
while i < vec.length() 
    sol.push_back(i) 
    i = i + 1 
    while i < vec.length() and vec[i] == vec[i-1] 
     i = i + 1 

溶膠是要

Answer 2

我覺得這個問題可以在O（N）來解決，最好是O（n）和最壞爲O（2N）

Answer 3

蟒你只是去向量：

set([(1,2), (2,3),(1,2)] 

在C++

，你可以使用和unordered set：http://www.cplusplus.com/reference/unordered_set/unordered_set/

使用pair<int,int>爲您點

Answer 4

，這是O到位的解決方案（N log n）的時間。

sort(vec.begin(), vec.end()); 
auto new_size = unique(vec.begin(), vec.end()) - vec.begin(); 
vec.resize(new_size);