我正在辅导一名学生，她的作业之一是描述一维情况下最接近点对的O（nlogn）算法。但限制是她不能使用分而治之的方法。我从一位用户几年前发布的一个问题中理解了二维案例。如果有人想看的话，我会把它链接起来：对于二维情况（平面）——"最近点对"算法。
然而，对于一维的情况，我只能想到一个解决方案，它包括检查线上的每一个点，并将其与最靠近它左右的点进行比较。但这个解决方案不是O（nlogn），因为检查每个点需要与n成比例的时间，而每个点的比较需要与2n成正比的时间。如果不使用分而治之的方法，我不确定log（n）会从哪里来。
出于某种原因，我无法想出解决方案。如有任何帮助，我们将不胜感激。
提示：如果点是从左到右排列的，你会怎么做，复杂度是多少？先对点排序的复杂性是什么？
在我看来，一个人可以：
- 将位置按顺序排序-O（n log n）
- 查找排序位置之间的差异-O（n）
- 求最小差-O（n）
- 最小的差异定义了两个最接近的点
总的结果是O（n log n）。