最小化總和的元素？

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).我想我能做的所有元素的總和aritmetic在載體和說，是平均我們正在尋找的一個。

但這是不正確的。例如：

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

，但如果我們考慮= 10，我們得到

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

另一種解決方案，我能想到的將是一個強力的最小元素最高與i += 0.1

一步

Answer 1

您正在尋找median - 而不是平均水平。

這是因爲你正在尋找的實際上是geometric median - 如果你只有一個維度（和你一樣），恰好是標準中位數。

中位數可以在O(n)使用Selection Algorithm - 所以排序是多餘的。