有可能找到在O(n)时间内差最小的两个数吗？

Question

给定一个未排序的整数数组，并且不对数组中的数字作任何假设：

有可能找到在O(n)时间内差最小的两个数字吗？

编辑:两个数字a，b之间的差被定义为abs(a-b)

Answer 1

查找列表中最小和最大的元素。差别最小-最大将是最小的。

如果您正在寻找非负差异，那么这当然与检查数组是否有两个相同的元素一样困难。这称为元素唯一性问题，不需要任何附加的假设(例如限制整数的大小，允许进行比较以外的其他操作)，这需要>= n日志时间。这是寻找最近对点的一维情况.

Answer 2

我认为你在O(n)中做不到。我能想出的最好办法是对它们进行排序(即O(n * log n))，并在排序列表中找到相邻对的最小差(这会添加另一个O(n))。

Answer 3

我认为这是可能的。秘密是，你不需要对列表进行排序，你只需要创建一个数字的统计。从算法的角度来看，这可以算作“假设”，而不是从实际的角度。我们知道ints有一个最小和一个最大值。

因此，创建一个由2位元素组成的数组，从INT_MIN到INT_MAX包含的每个int设置为1对，将它们全部设置为00。

遍历整个数字列表。对于列表中的每个数字，如果对应的2位为00，则将其设置为01。如果他们是01，把他们设为10。否则忽略。这显然是O(n)。

接下来，如果2位中的任何一位被设置为10，这就是您的答案。最小距离为0，因为列表包含一个重复的数字。如果没有，则扫描列表并找到最小距离。许多人已经指出这方面有一些简单的O(n)算法。

所以O(n) + O(n) = O(n)。

编辑:回应评论。

有趣的地方。我认为，通过先找到列表的min/max并使用从min到max之间的稀疏数组来保存数据，您可以获得相同的结果，而无需做任何假设。考虑了阵列扫描的INT_MIN/MAX假设、空间复杂度和O(m)时间复杂度。