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

您正在寻找中位数- 而不是平均值。

这是因为您正在寻找的实际上是几何中位数- 如果您只有一个维度（并且您确实有），这恰好是标准中位数。

中值可以在O(n)使用选择算法中找到- 所以排序是多余的。