我正在辅导一名学生，她的一项作业是为一维情况下最近的点对描述 O(nlogn) 算法。但限制是不允许她使用分而治之的方法。我从几年前用户发布的一个问题中了解到二维情况。我会链接它以防有人想看它:对于二维案例(平面)- "Closest pair of points" algorithm .
但是，对于一维情况，我只能想到一种解决方案，即检查直线上的每个点并将其与距离它左右最近的点进行比较。但是这个解决方案不是 O(nlogn)，因为检查每个点将花费与 n 成正比的时间，而每个点的比较将花费与 2n 成正比的时间。如果不使用分而治之的方法，我不确定 log(n) 的来源。
出于某种原因，我想不出一个解决方案。任何帮助将不胜感激。
最佳答案
提示:如果点从左到右排列，你会怎么做，复杂度是多少？先排序点的复杂度是多少？
关于algorithm - 最近点对(线性一维情况)算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26289829/