Q) 在给定的一组点中找到最近的一对点。
预期时间复杂度：O(n log2(n)) / O(n log(n))
我正在从这里阅读这个问题。但是我无法理解一些事情：
我们通过 Y 对已经按 X 排序的点进行排序来实现什么？
当我们从其中一个半场中取一个点时，我们不会错过一些案例吗？即，如何取中点确保形成的条带包含所有候选点，其距离小于两个递归调用返回的距离？
即使证明了上述点，我们是否应该取两半的中点，即左半边的m和右半边的(m+1)？
问问题
501 次
2 回答
2
2）您使用中点的 x 坐标找到将点一分为二的线。递归调用比较所有不越过该线的对，因此剩下的就是比较确实越过该线的对。如果两点之间的距离小于d ，并且它们位于直线的任一侧，那么它们距离直线的距离都必须小于d 。
3）嗯，这将在递归调用中完成。我不知道你还有什么意思。
1）条带中的点被分离出来并排序。然后，给定条带中的一个点，所有 y 坐标在d内的点都在它周围的一个连续区域中。这些是您唯一需要与之比较的其他点，并且排序使您可以快速轻松地找到这些点。该算法的神奇之处在于，任何此类区域中可能的点数都严格限制为一个常数值。这是因为（由递归调用确定）直线两侧没有任何一对点比d更近。
于 2020-06-01T13:50:12.550 回答
1
如果我理解正确的话，以下几点实际上有点误导：
3）递归地找到两个子阵列中的最小距离。[...]
我认为它应该说：递归地拆分子数组，直到它们包含少量点（可能是 2 或 3？它没有说），然后在每个小条中找到最小的距离。然后我们继续 4)-7) 并对我们创建的所有子数组之间的每个边界应用 y 条搜索。
这是我对发生的事情的理解，它没有提到数组拆分，因为我认为这只会混淆正在发生的事情：
1) 按 x 对所有点进行排序。遍历排序数组并计算每对连续点的距离，即。每个点和它后面的点。我们得到一个最小距离' d '。
2) 按 y 对所有点进行排序。同样，对于每个点，我们计算到排序数组中其直接跟随邻居的距离。与 '1)' 不同，我们不仅考虑直接邻居，还考虑所有在当前点之前小于 ' d ' 的邻居。当我们找到距离更小的 ' d ' 的一对时，我们从这一刻起使用这个新的距离作为我们的新的 ' d '。
这应该给我们最小的d。
基本上，递归地拆分数组直到只剩下对（我猜他们暗示的）实际上与简单地遍历数组并比较每个连续的点对相同。不过，我的步骤 1）有一个区别：它们只计算每个第二个点到其后继点的 x 距离（每个第二个点之后都有一个子数组边界）。这可能会有所帮助（因为他们只完成了一半的工作）或有害（因为他们可能无法从第一次通过中获得最好的d）。
我还没有验证这一点，如果我理解错误或者我的“翻译”方法有问题，请告诉我。
于 2020-06-02T22:02:54.530 回答