algorithm - 如何在一维中找到一组唯一的最近点对？

唯一的区别是我是一维的。

所以，我有两组点（因为我在 1D 中，我们可以将它们视为 0 到 1 之间的数字）A 和 B，每个点分别包含 m 和 n 元素，m<=n

我的目标是找到集合 C，由 B 中的 m 个 DISTINCT 点组成，以最小化距离之和 [A(i), C(i)] 如果 m = n，我可以使用具有很好的一维实现的 wasserstein 距离在 2D 中，我会使用匈牙利算法，但它相当昂贵，我希望 1D 有更快的解决方案。

谢谢

标签： algorithmgeometryclosest

大声思考：

对于 A 中的每个点，在两侧找到 B 中最近的两个点是一件容易的事。因为这足以对 A 和 B 进行越来越多的排序，并且通过类似合并的过程，您可以在 A 的每个点的 B 中找到前任和后继。

这个过程的成本是 O(NA Log NA) + O(NB Log NB) + O(NA + NB)，其中最后一项可以被吸收。

最小的总和将通过为每个点分配其最近的邻居来实现，在左侧和右侧。

到目前为止一切顺利，但不幸的是，最近的邻居也可能是离 A 中的相邻点最近的，并且需要仲裁冲突（必须将 A 点之一分配给它的另一个 B 邻居）。在最坏的情况下，这可能会导致级联冲突。

到目前为止，我担心这个问题是全球性的，我认为没有比尝试以所有可能的方式解决冲突并保持最佳配置更好的方法了。这个过程在冲突点序列的长度上是指数的。