Q）在给定的点集中寻找最接近的点对。
预期的时间复杂度。O(nlog2(n)) O(nlog(n))
我阅读了这个问题从 此处. 然而，我无法理解一些事情。
我们通过对已经按X排序的点按Y排序来实现什么？
当我们从其中一个半部分取一个点作为中点时，我们不是会错过一些情况吗？也就是说，取一个中点如何确保形成的条带包括所有的点，这些点的候选距离小于两个递归调用返回的距离？
即使上述观点被证明，我们是否应该取两半的中点，即左半的m和右半的(m+1)？
2）你用中点的x坐标找到一条将点一分为二的线。 递归调用比较所有的对 不要 越过那条线，所以剩下的就是比较那些 做 过线。 如果两点小于 d 相隔，并且它们在线的两边，那么它们一定都小于。d 离线。
3）嗯，这将在递归调用中完成。 我不知道你还有什么意思。
1）条带中的点被分离出来，并进行排序。 然后，给定条带中的一个点，所有点的y坐标在 d 是在它周围的一个连续区域。 这些是你唯一需要和它进行比较的其他点，而排序使你能快速、轻松地找到这些点。 这个算法的神奇之处在于，在任何这样的区域中，可能的点的数量被严格限制在一个常数。 这源于这样一个事实（由递归调用建立的），即线两侧的任何一对点都不比 d.
如果我理解正确的话，下面的观点其实有点误导。
3) 递归地找到两个子数组中最小的距离。[...]
我认为应该说。递归地分割子数组，直到它们包含一小部分点(可能是2或3个?它没有说)，然后在每一个这小条中找到最小的距离。然后我们继续进行4)-7)，对我们创建的所有子数组之间的每个边界应用y条搜索。
这是我对发生的事情的理解，它没有提到数组拆分，因为我认为这只会混淆事情的真相。
1) 将所有的点按x进行排序，在排序后的数组上行走，计算每对连续点的距离，即每个点和它后面的点的距离。我们得到一个最小距离'。d'.
2）按y对所有点进行排序，同样，对于每一个点，我们计算其与排序数组中的直系邻域的距离，与'1)'不同的是，我们不仅考虑直系邻域，还考虑所有小于''的邻域。与'1)'不同的是，我们不仅考虑直接的邻居，而且考虑所有小于''的邻居。d'的当前点前方.当我们发现一对距离小于'd'，我们用这个新的距离作为我们新的'。d'从这一刻开始。
这应该给我们最小的 d.
基本上，递归拆分一个数组直到只剩下对子（我想这就是他们所暗示的），实际上和简单地走过数组并比较每一个连续的点对是一样的.我的步骤1)有一个不同之处：他们只计算第2个点到它的继承者的x距离（在每第2个点之后有一个子数组边界）。这可能会有帮助（因为他们只做了一半的工作），也可能会有坏处（因为他们可能得不到最好的结果）。d 从这第一道）。)
我还没有验证，如果我理解错了，或者我的 "翻译 "方法有问题，请告诉我。