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

Question

给定一个未排序的整数数组,并且不对数组中的数字做任何假设:
是否有可能找到两个在O(n)时间内差异最小的数字？

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

Answer 1

查找列表中的最小和最大元素.最小的差异将是最小的.

如果你正在寻找非负差异,那么这当然至少和检查数组是否有两个相同元素一样困难.这称为元素唯一性问题,并且没有任何其他假设(如限制整数的大小,允许除比较之外的其他操作)需要> = n log n时间.它是找到最近点对的一维情况.

Answer 2

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

@fbrereto:基数排序不是O(n),它是O(kn),其中k是数组中值的位数.如果我们知道k很小,我们可能会使用基数排序并获得一些东西.由于我们不知道值的范围,我们不能假设k小于log n. (4认同)
我的想法是一样的但是@Michael Todd说你可以在O(n)中做到这一点所以我迫不及待地想看看他发布了什么 (3认同)