查找离阵列中所有数字最近的数字

我们有一个包含n个元素的列表。例如， {n1,n2,n3...nk} 这个列表进行排序，我们必须找出的数量ni是

有可能是总(nk-n1+1)可能的数字，但我们的目标是找出哪些是最近的所有其他号码的数量ni。

蛮力方法可以遍历n1到nk并计算距所有列表号码的距离的总和。通过这种方式，我们可以很容易地找出与列表中所有其他数字最接近的数字。

但是这种方法的问题是，它在时间复杂性方面不好。这种方法的时间复杂度为O(n^2)。

我认为可以有更好的方法来做到这一点，可以用更少的时间来解决这个问题。

任何方法将不胜感激。

2013-02-26 vicky

你使用什么定义的“距离”？ – 2013-02-26 13:25:20

如何搜索二进制搜索因为你提到该列表是排序？ – kamaci 2013-02-26 13:26:41

是距离（a，b）= abs（ab） – vicky 2013-02-27 05:26:16

如果用“距离”表示distance(a,b) = abs(a-b)那么你只需要找到中位数。

查找排序列表中的中位数为O（1）。

2013-02-26 13:27:46

您可能的意思是“medoid”（如果存在奇数个元素，则其值与给定距离定义（abs（ab））的1d情况下的中值一致）。 – jfs 2013-02-26 13:56:55

@塞巴斯蒂安：是的，我知道。如果有偶数个元素，则任一/两个medoids都可以。 – 2013-02-26 14:08:30

是的，如果有偶数个元素。那么最近的数字应该是两个中间数字的平均值。如果b1和b2是两个中间数字，那么最近的数字应该是（b1 + b2）/ 2。 – vicky 2013-02-27 05:31:31

查找平均值......这需要O（n）。然后通过列表找到ni的平均值（也需要O（n））...实际上更像o（1/2n）

2013-02-26 13:33:02

答案应该是ROUND（SUM（n1，...， nk）/ k）。

2013-02-28 07:53:39 Richard

回答