找到一个数组中绝对差的最小总和的数字

Question

例如，array a[]= {1,1,10}我们需要找到|x-1|+|x-1|+|x-10|最小的“x” 。
在这里，x 是 1。

它可以用贪婪的方法解决吗，比如取平均值或其他什么？
注意：取平均值不起作用，为什么？

我只能想出O(nlogn)解决方案（二进制搜索），还有其他方法如 dp 吗？

提前致谢！

Answer 1

这是一个非常简单的问题（不要觉得被冒犯了：至少，如果你知道，答案很简单）：

如果您有奇数个项目，那么中间的那个将是您的最佳选择。

如果您有一个偶数，则中间两个之间的任何数字都将是同样最优的。

所以不需要数值计算，只需要排序:)

解释：移动你得到的数字将改变每个abs(x-x1)相同的数量，但具有不同的符号：一些增加，一些减少。

从中心点（在奇数情况下）abs向任一方向移动时，都会增加一个；而当在两个中心点之间移动时（在偶数情况下）abs，每个符号的数量将相同。