在一个数组中找到最接近所有数字的数字

Question

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

我们有一个包含n个元素的列表，例如{ n1， n2， n3 ... nk }。这个列表已经排序好了，我们需要找到符合以下条件的数字ni：

1. n1 <= ni <= nk
2. ni与其他所有数字的距离之和最小。

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

蛮力方法是遍历n1到nk，并计算与列表中所有数字的距离之和。这种方式容易找出最接近所有其他数字的数字。

但是这种方法的问题在于，从时间复杂度的角度来看不够好。该方法的时间复杂度为O(n^2)。

我认为可能有更好的方法解决这个问题，可以使用更少的时间复杂度。

欢迎提任何方法。

- vicky

---

你使用哪种“距离”的定义？ - Klas Lindbäck

既然你提到列表已经排序，那么使用二分查找怎么样？ - kamaci

是的，distance(a,b)=abs(a-b)。 - vicky

Answer 1

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

在有序列表中找到中位数的时间复杂度为O(1)。

- Klas Lindbäck

---

你可能指的是“medoid”（在给定距离定义（abs(a-b)）下，如果元素数量为奇数，则其值与1d情况下的中位数重合）。 - jfs

@Sebastian：是的，我有。如果元素数量为偶数，则任何/所有中心点都可以。 - Klas Lindbäck

如果元素数量为偶数，则最接近的数字应该是两个中间数字的平均数。如果b1和b2是两个中间数字，则最接近的数字应该是（b1+b2）/2。 - vicky

如何在已排序的列表中以O(1)时间复杂度获取中位数？ - vicky

Answer 2

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

- Richard

Answer 3

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

- Michel Keijzers