rka*_*yar 23 algorithm optimization
给定一个未排序的整数数组,并且不对数组中的数字做任何假设: 是否有可能找到两个在O(n)时间内差异最小的数字？
编辑:两个数字a,b之间的差异定义为abs(a-b)
abs(a-b)
sdc*_*vvc 22
查找列表中的最小和最大元素.最小的差异将是最小的.
如果你正在寻找非负差异,那么这当然至少和检查数组是否有两个相同元素一样困难.这称为元素唯一性问题,并且没有任何其他假设(如限制整数的大小,允许除比较之外的其他操作)需要> = n log n时间.它是找到最近点对的一维情况.
Bil*_*ard 6
我不认为你能在O(n)中做到这一点.我能想到的最好的方法是对它们进行排序(即O(n*log n))并找到排序列表中相邻对的最小差异(这会增加另一个O(n)).
归档时间：
15 年，10 月 前
查看次数：
9479 次
最近记录：
13 年，11 月 前