我正在尝试执行最接近的配对算法- 但是有一个区域我完全卡住了。
可以使用递归分治法在 O(n log n) 时间内解决该问题，例如，如下所示：
1) 根据 x 坐标对点进行排序。
2) 通过垂直线 x=xmid 将点集分成两个大小相等的子集。
3) 在左右子集中递归求解问题。这分别产生左侧和右侧最小距离 dLmin 和 dRmin。
4) 找出一组点对中的最小距离dLRmin，其中一个点位于分界线的左侧，第二个点位于右侧。
5) 最终答案是 dLmin、dRmin 和 dLRmin 中的最小值。
我的问题在于第 3 步：假设您已将 8 个元素的数组分成两半，在左半部分有 4 个点 - 1、2、3 和 4。假设第 2 点和第 3 点是这 4 个点中最接近的一对。好吧，如果你继续递归地把这个子集分成两半，你最终会计算出 1-2 之间的最小值（左边），你会计算 3-4 之间的最小值（右边），然后你会返回这两对的最小距离对..
但是 - 你完全错过了 2-3 之间的距离，因为你从来没有计算过，因为他们在对立面......那么这个问题是如何解决的呢？请注意第 4 步是如何在这个递归过程之后出现的，它似乎是一个独立的步骤，并且仅适用于第 3 步之后的最终结果，而不适用于第 3 步中发生的子数组的每个后续划分。是吗？还是有另一种我想念的方法？