查找离阵列中所有数字最近的数字
问题描述:
此问题基本上是算法优化问题。查找离阵列中所有数字最近的数字
我们有一个包含n个元素的列表。例如, {n1,n2,n3...nk}
这个列表进行排序,我们必须找出的数量ni是
n1<=ni<=nk
- 的
ni
距离的每个数字之和是最小的。
有可能是总(nk-n1+1)
可能的数字,但我们的目标是找出哪些是 最近的所有其他号码的数量ni
。
蛮力方法可以遍历n1
到nk并计算距所有列表号码的距离 的总和。通过这种方式,我们可以很容易地找出与列表中所有其他数字最接近的数字。
但是这种方法的问题是,它在时间复杂性方面不好。这种方法的时间复杂度为O(n^2)
。
我认为可以有更好的方法来做到这一点,可以用更少的时间来解决这个问题。
任何方法将不胜感激。
答
如果用“距离”表示distance(a,b) = abs(a-b)
那么你只需要找到中位数。
查找排序列表中的中位数为O(1)。
答
查找平均值......这需要O(n)。 然后通过列表找到ni的平均值(也需要O(n))...实际上更像o(1/2n)
答
答案应该是ROUND(SUM(n1,..., nk)/ k)。
你使用什么定义的“距离”? – 2013-02-26 13:25:20
如何搜索二进制搜索因为你提到该列表是排序? – kamaci 2013-02-26 13:26:41
是距离(a,b)= abs(ab) – vicky 2013-02-27 05:26:16