我是编码的新手，今天我完成了二维空间中最近对问题的平凡解决方案。 （2个循环）
但是我放弃了找到任何可以在O（n log n）中实现的解决方案。即使进行了研究，我仍然不知道如何比简单的方法更快。
我的理解： ->首先，我们将数组分成两半，并仅考虑X坐标对所有内容进行排序。这可以在n log n中完成。
接下来，有一个递归调用，它们在每一半中“找到距离最小的两个点”。 但是如何恰好在O（n ^ 2）以下呢？ 以我的理解，如果不检查每个N / 2点，就不可能找到N / 2点之间的最小距离。
一维解决方案对我来说绝对有意义。排序后，我们知道两个不相邻点之间的距离不能小于至少两个相邻点之间的距离。但是，对于二维空间，情况并非如此，因为我们还有一个额外的Y坐标，这可能导致X轴上不相邻的两个点之间的距离最小。
首先，请注意@Evg用户的建议-此答案不能替代算法的全面描述和严格的数学分析。
但是，这里有一些想法可以帮助您开始直觉：
（递归结构） 问题指出：
接下来，有一个递归调用，它们在每一半中“找到距离最小的两个点”。但是如何精确地在O（n ^ 2）以下呢？以我的理解，如果不检查每个N / 2点，就不可能找到N / 2点之间的最小距离。
但是，递归不会在第1层停止-出于争论的原因，假设某些O(n log n)算法有效。应用该算法在N/2个点中查找最接近的对需要O(N/2 log N/2)而不是O((N/2)^2)。
（在一半中找到最接近的对的结果）
如果在点集的“左”一半中找到了最接近的一对(p,q)，则该对的距离将设置一条距离，该距离是一条对分线周围的走廊宽度的上限，距离更近的一对(r,s)使用左侧的r，可以绘制右侧的s。如果到目前为止找到的最近距离为“小”，则将大大减小候选集的大小。由于这些点已按其x坐标进行排序，因此该算法可以有效地利用信息。
所述走廊仍然可以覆盖整个N点集合，但是如果覆盖了整个范围，它可以提供点集合的几何信息：每半个点都将基本上沿着一条垂直线对齐。可以通过算法利用此信息-最幼稚的方法是再次执行算法，但沿y坐标排序，并将水平线设置的点减半。请注意，将任何算法执行恒定的次数不会更改由O(.)表示的渐近运行时间。
（找到一个一对，每个半点各有一个点）
考虑检查一对点(r,s)，每半点一个。众所周知，它们的x和y坐标之差不得超过到目前为止找到的最小距离d。从递归得知，r',s'（从左边的r'到右边的s'）比{ {1}}。因此，给定一些r,s，那么另一半就不可能有“很多”候选人。
想象一个围绕d绘制的半径为r的圆。距另一半d较r更近的任何点都必须位于该圆内。让它们中的一些-但是，每对之间的最小距离仍然至少为s。半径为d的圆内可以分布的最大点数，使得它们之间的距离至少为d为7-考虑边长为d的正六边形及其中心与圆心重合。
因此，在递归之后，最多需要检查左半边的每个d的最大值，而另一半则最多要检查一个恒定的点数，这使得递归在d中运行之后，算法的一部分。
请注意，找到给定r的配对候选对象是一种有效的操作-来自两个半部分的点已按照相同的标准进行了排序。