我是编码的新手,今天我完成了二维空间中最近对问题的平凡解决方案。 (2个循环)
但是我放弃了找到可以在O(n log n)中实现的任何解决方案。即使经过研究,我仍然不知道如何比简单的方法更快。
我的理解:->首先,我们将数组分成两半,并仅考虑X坐标对所有内容进行排序。这可以在n log n中完成。
[接下来有递归调用,它们在每一半中“找到距离最小的两个点”。 但是在正好在O(n ^ 2)以下如何进行呢?以我的理解,如果不检查每个N / 2点,则不可能找到N / 2点之间的最小距离。
一维解决方案对我来说绝对有意义。排序后,我们知道两个不相邻点之间的距离不能小于至少两个相邻点之间的距离。但是,对于二维空间,情况并非如此,因为我们还有一个附加的Y坐标,这可能导致X轴上不相邻的两个点之间的距离最小。]
我是编码的新手,今天我完成了二维空间中最近对问题的平凡解决方案。 (2个循环)但是我放弃了在O(n log n)中可以找到的任何解决方案。甚至...
首先,请注意用户@Evg的建议-此答案不能替代对该算法的全面描述和数学上严格的分析。