如地球人都知道的那样,这道题用并查集就好了,
但很多人用了快排离散化,每次找点的时候用2分查找,
其实这一题中,点与点之间的位置关系不是很重,在解题中可以看到,并没有起到作用,因此是不需要离散化的,所以用一个哈希表来查找,效果更好,可以将时间从O(nlogn)降到O(N)
但很多人用了快排离散化,每次找点的时候用2分查找,
其实这一题中,点与点之间的位置关系不是很重,在解题中可以看到,并没有起到作用,因此是不需要离散化的,所以用一个哈希表来查找,效果更好,可以将时间从O(nlogn)降到O(N)