algorithm - 在 O(n) 中找到最近元素之间的距离

Question

有一个无序的n整数数组。我想找到 O(n) 中两个元素之间的最短距离。

谢谢！

注意：由于时间复杂性，基数排序不适合。

Answer 1

在计算的代数决策树模型中，这是一个 Ω(n log n) 问题。限制为无界整数并没有真正的帮助。