algorithm - 按最近点对位置数组进行排序

Question

所以问题是这样的:

Given a location X and an array of locations, I want to get an array of locations that are closest to location X, in other words sorted by closest distance.

我解决此问题的方法是遍历每个位置数组并计算 X 与该特定位置之间的距离，存储该距离，然后使用比较器按距离对位置进行排序。完毕!有一个更好的方法吗？假设排序是归并排序，应该是O(n log n)。

Answer 1

如果我没有理解错的话，您可以非常快速地对多个查询执行此操作 - 例如，给定多个 X 值，您不必每次都对解决方案数组进行重新排序。方法如下:

1. 最初对数组进行排序(O(n logn) - 称之为预处理)
2. 现在，在每个查询 X 上，对数组进行二进制搜索以查找 X(或小于 X 的最接近数字)。维护两个索引，i 和 j，一个指向当前位置，一个指向下一个。其中之一显然是列表中最接近 X 的数字。选择距离较小的一个并将其放入您的解决方案数组中。现在，如果选择了 i，则减少 i - 如果选择了 j，则增加 j。重复此过程，直到所有数字都在解决方案数组中。

对于每个具有 O(nlogn) 预处理的查询，这需要 O(n + logn)。当然，如果我们只谈论一个 X，那一点也好不到哪儿去。