arrays - 查找最接近数组中所有数字的数字

Question

这个问题基本上是一个算法优化问题。

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

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

蛮力方法可以迭代n1到 nk 并计算与所有列表编号的距离之和。通过这种方式，我们可以轻松找出最接近列表中所有其他数字的数字。

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

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

任何方法将不胜感激。

score 7 · Accepted Answer

如果你的意思是“距离”，distance(a,b) = abs(a-b)那么你只需要找到中位数。

在排序列表中找到中位数是 O(1)。

score 1 · Accepted Answer

1

答案应该是 ROUND( SUM(n1,...,nk)/k ) 。

于 2013-02-28T07:53:39.290 回答

score 0 · Accepted Answer

求平均值……这需要 O(n)。然后遍历列表以找到平均值的 ni（也需要 O(n)）...实际上更像 o(1/2n)

3 回答 3