algorithm - 在 O(n log n) 时间内找到一个集合中的两个不同数字，使得它们的差是所有对中最小的

Question

如何在 O(n log n) 时间内在未排序的集合 S 中找到两个不同的数字 a 和 b，以便 |ab| 是所有可能的对中最小的吗？

Answer 1

首先，使用快速排序对列表进行排序，即 O(n log n)。

然后对列表进行一次遍历，测量每个数字与下一个数字之间的间隔，并跟踪您看到的最小间隔。那是 O(n)。

O(n) + O(n log n) = O(n log n)