最小化 Array 的每个元素与整数 K 之间的差值总和

Question

给定一个由 N 个非负整数组成的数组 A，找到一个整数 k，使得每个元素与 k 的差之和最小。
即求和(abs(A[i] - k)), 1 <= i <= N，或简单地
|A[1] - k| + |A[2] - k| + |A[3] - k| + ... + |A[N] - k|

我的方法：

low = minimumValueInArray(A);
high= maximumValueInArray(A);
ans = Infinite;
for (k = low; k <= high; k++) {
    temp = 0;
    for (i = 1; i <= N; i++) {
        temp += abs(A[i] - K);
    }
    ans = min(ans, temp);
}
return ans;

这只是试图解决所有 K 值的蛮力方法。我们可以优化它吗？
这样做的更聪明的方法是什么？

参考：这是我在Codejam Round 1B 问题背后的逻辑

Answer 1

我基本上得到了中位数。为了最小化成本函数，取导数。

要找到成本函数的最小值，请找到导数为零的位置。成本函数不是处处连续可微的，而是分段可微的。令 S = A 的排序数，si 为第 i 个最大数。

情况 1. 如果 m 是奇数

将有 floor(m/2) ai 小于中位数和 floor(m/2) ai 大于中位数。选择 x = 中位数，得到 -m/2 + 0 + m/2 = 0。

情况 2. 如果 m 是偶数

对于 si 和 s(i+1) 之间的值，导数为零；我 = 米/2。然后可以选择任意数 k 使得

简单示例 1 2 4 50

选择 2：1 + 0 + 2 + 48 = 51

选择 4：3 + 2 + 0 + 46 = 51

选择 3：2 + 1 + 1 + 47 = 51

所以随意挑s(m/2)

对于更好的算法，O(NlogN)，您可以对数字进行排序，然后根据需要从上面选择 (m+1)/2 或 m/2，或者您可以使用可以在 O(N) 中计算答案的第 k 个最大元素.