Closest Pair -
分
治法
【
算
法
思
想
】
首先对所有的点按照x坐标进行从小到大的排序，然后利用二分法进行分割，知道区间范围变为2 或者3，然后求出
这2个点或者3个点的距离。
对于每一部分的子问题，还需要考虑边界附近点与另一个集合点之间的距离。
怎样考虑相邻子问题之间两个点的距离是否会小于两个子问题内部的最小距离min_len呢？
一个暴力的方法是嵌套循环遍历两个子问题的所有点求出两个子问题之间的最小距离。显然，时间复杂度为
O(n^2)。
我们是否可以做的更好？
考虑下图：
从上图可以看出，实际上我们只需考虑离边界线的距离小于min_len的点就行。
评论0