algorithm - 使总和最小的元素？

Question

我发现了一个问题:

Let's consider a vector x = (x1, x2 ... xn) with real elements. 
1). Sort the vector  -- easy
2). Find a real number a so that sum ( abs (xi - a) ) is minim

我不知道对数组进行排序是否有帮助，但对于 2). 我想我可以对向量中的所有元素进行算术求和，然后说 avg 是我们的 a寻找。

但这是不正确的。示例:

x = (1, 10, 10)
avg = [ 21/3 ] = 7 = a
sum = |1 - 7| + |10 - 7| + |10 - 7| = 6 + 3 + 3 = 12

但是如果我们考虑 a = 10 我们得到

sum = |1 - 10| + |10 - 10| + |10 - 10| = 9 < 12

我能想到的另一种解决方案是从最小元素到最高元素的蛮力，步长为 i += 0.1

Answer 1

您正在寻找 median - 而不是平均值。

这是因为您要查找的实际上是 geometric median - 如果你只有一个维度(你有)，这恰好是标准中位数。

可以使用 Selection Algorithm 在 O(n) 中找到中位数- 所以排序是多余的。