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

Question

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

algorithmoptimization

23

给定一个未排序的整数数组，不做任何有关数组中数字的假设：
是否可能在O(n)时间内找到差值最小的两个数？

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

- rkatiyar

你能通过作弊的方式搜索相同的两个整数吗？因为它们之间的差值将是最小的。 - Anthony Forloney

@aforloney - 我认为“不对数组中的数字做任何假设”的要求会排除这种可能性。 - Eric Petroelje

@aflorloney：取决于您对“最小”的定义。（10-10）>（2-3）。 - Juliet

非常正确，我改正。 - Anthony Forloney

1

这个问题似乎定义不清。你的意思是要找到 min {abs(t[i]-t[j]): i=/=j} 吗？ - liori

显示剩余4条评论

8个回答

6

我认为你不能在O(n)的时间复杂度内完成这个任务。从我的经验来看，最好的方法是对它们进行排序（时间复杂度为O(n * log n)），然后在排序后的列表中找到相邻对之间的最小差值（这将增加另外的O(n)时间复杂度）。

- Bill the Lizard

3

我也这么想，但是 @Michael Todd 说你可以在O(n)的时间内完成，所以我急切地等待他发布的内容。 - non sequitor

@非正常情况：希望他能尽快回复我们。我很高兴被证明是错的。 :) - Bill the Lizard

我认为你很接近了——基数排序可以让你在O(n)的时间内完成排序，然后相邻对迭代需要O(n)的时间。 - fbrereto

4

基数排序的时间复杂度不是O（n），而是O（kn），其中k是数组中值的位数。如果我们知道k很小，我们可以使用基数排序并获得更好的效果。由于我们不知道值的范围，因此不能假设k比log n小。 - Bill the Lizard

@Michael Todd：我也只是随意说说而已。你最初的评论完全没问题。 - Bill the Lizard

显示剩余2条评论

2

我认为有可能。秘诀在于你实际上不需要对列表进行排序，只需创建一个计数器来记录存在哪些数字。从算法的角度来看，这可能被视为“做出假设”，但从实际角度来看并非如此。我们知道整数的范围由最小值和最大值限制。

因此，创建一个包含2位元素的数组，每个int从INT_MIN到INT_MAX都有一对，将所有元素设置为00。

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

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

因此，O（n）+ O（n）= O（n）。

编辑：回应评论。

有趣的观点。我认为你可以通过先找到列表的最小/最大值，并使用从min到max的稀疏数组来保存数据来实现相同的结果。解决了INT_MIN / MAX假设、空间复杂度和扫描数组的O（m）时间复杂度问题。

- patros

谁说它正在实现有限大小数字的系统中？ - nobody

1

如果您的算法依赖于整数被最小值和最大值所约束，那么它实际上是O（1）的。假设n有一个最大值，那么操作将需要有限的时间。 - David Thornley

你的数组长度不是O(n)，但你假设它被初始化为00元素。此外，你如何扫描列表以找到最小距离？ - meriton

但从“实际角度”来看，处理32位（或更糟糕的64位）整数时，运行时间将是天文数字级别的。运行时间为O(1)，但常数成本确实很高 :) - hythlodayr

4

这是 O(n) + O(m) = O(n + m)，其中 n = <元素数量>，m = <整数大小>。 - tster

1

我能想到的最好方法是使用计数排序数组（可能会合并相等的值），然后进行排序比较--桶排序的时间复杂度为O(n + M)（其中M是不同值的数量）。然而，这需要大量的内存。某种形式的桶或基数排序在时间上处于中间位置，并且在空间上更加高效。

- Kathy Van Stone

你可能需要使用基数排序，对吧？因为你没有给出数字的可能范围，所以计数排序会立即被排除在外。 - Andrew Song

找到范围是一个O(n)操作（最小值，最大值）。 - Kathy Van Stone

是的，但在这种情况下，范围可以任意大。请参见Bill the Lizard在他的回答中的评论。 - PeterAllenWebb

@Peter，不可能。范围不能大于数据类型的最大值减去最小值。 - Joshua

3

我们正在讨论渐近分析。发帖者并没有询问32位整数或64位整数的问题。他很可能在使用任意精度整数。我知道这似乎是个学究式的区分，但如果不做出这个区分，你就可以声称以O(n)的时间对任何整数列表进行排序，而我们知道这是不可能的。 - PeterAllenWebb

计数排序的时间复杂度为O(n + k)，其中k是值范围的大小，而不是不同值的数量。 - meriton

1

使用基数排序（对于整数是O(n)）对列表进行排序，然后迭代并跟踪到目前为止最小的距离。

（我假设您的整数是固定位类型。如果它们可以容纳任意大的数学整数，则基数排序也将是O(n log n)。）

- meriton

我认为在这里不能保证k是常数。如果k=n怎么办？ - Andrew Song

3

基数排序之所以只需要 O(n) 的时间复杂度，是因为该算法已经将限制条件融入其中。如果你要对普通的 int 类型的数值进行排序，而且这些数值保证唯一，那么实际上时间复杂度是 O(1)。但如果你要对任意大的数字进行排序，那么时间复杂度就不再是 O(n)了。 - David Thornley

你说得对，整数可能指的是可变长度的数据类型。我已经编辑了我的答案来说明这个假设。 - meriton

1

似乎可以在O(n*sqrt(log(log(n)))时间内对无界整数集进行排序。排序后，当然可以轻松地在线性时间内找到最小差异。

但我想不出比这更快的算法。

- liori

0

不行，除非对数字/排序进行假设。

如果给定一个已排序的列表，那么是可能的。

- chills42

0

我认为答案是否定的，证明类似于你不能比n lg n更快地排序的证明：你必须比较所有元素，即创建一个比较树，这意味着omega(n lg n)算法。

编辑。好吧，如果你真的想争论，那么问题并没有指明它应该是图灵机还是不是。使用量子计算，您可以在线性时间内完成：)

- Denis Tulskiy

为什么你必须比较所有的元素？显然你需要查看它们，但是为什么要比较？ - meriton

1

好的，我们称之为“数字观察”，无论如何，都会有一个比较树。 - Denis Tulskiy

你仍然假设每个解决此问题的好算法都会进行比较并构建比较树。由于你没有证明这个假设，因此你的证明是不完整的。 - meriton

使用整数数据类型可以更好地处理数据，因为我们不仅仅只有简单的顺序关系，还可以获得更多关于数据集的信息。例如，如果我们知道数据集由K种不同类型的值组成，可以使用计数排序算法并达到O(n+K)的时间复杂度。请参阅我的回答。 - liori

我想说的是，任何算法都必须检查每一对可能的数字，这是omega(n lg n)。 - Denis Tulskiy

即使您可以在sub-nlog（n）时间内对无界整数进行排序？请确实检查我的答案。 - liori

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sdcvvc · Accepted Answer

查找列表中最小和最大的元素。最小值与最大值之差将是最小的。

如果你要寻找非负的差异，那么这至少跟检查数组是否有两个相同的元素一样难。这被称为元素唯一性问题，在没有任何其他假设条件（比如限制整数的大小，允许除了比较以外的操作）的情况下需要>= n log n时间。它是查找最近点对的一维情况。