mingap专题

二,几何相交---1,预备---(2)MinGap最小缝隙

最小缝隙顾名思义,找到相邻的两个元素的最小缝隙。类似于EU,先进行排序,然后两两比较相邻的差值,得出最小的那个。不妨想下,如果差值为0,则元素不唯一;如果差值不为0,则元素唯一。这正是EU算法。所以,可以把EU问题归结到到mingap,时间复杂度o(nlogn)