arrays - 求 A[i] 与常数之差的最小总和

Question

对于一项作业，我需要解决一个数学问题。我将其缩小为以下内容:

令 A[1, ... ,n] 为 n 整数数组。

令y 为整数常量。

现在，我必须编写一个算法，在 O(n) 时间内找到 M(y) 的最小值:

M(y) = Sum |A[i] - y|, i = 1 到 n。请注意，我不仅采用 A[i] - y，还采用绝对值 |A[i] - y|。

为清楚起见，我还将此等式放在 Wolfram Alpha 中.

我考虑过最小二乘法，但我认为这不会产生 M(y) 的最小值，而是更多的 A 的平均值。由于我采用的是 A[i] - y 的绝对值，因此我也无法将此函数与 y 区分开来。此外，我不能想出任何算法，因为我必须在 O(n) 时间内完成。此外，我相信在某些情况下 y 可以有更多正确答案，在这种情况下，y 的值必须等于 的整数元素之一>A.

这真的困扰了我整整一个星期，但我仍然没有弄明白。任何人都可以教我走的路或指出正确的方向吗？我卡住了。非常感谢您的帮助。

Answer 1

您想为 M(y) = sum(abs(A[i] - y)) 选择一个 y是最小的。让我们假设每个 A[i]是正数(它不会改变结果，因为问题是平移不变的)。

让我们从两个简单的观察开始。首先，如果你选择 y 这样 y < min(A)或 y > max(A) ，你最终得到的 M(y) 值比你选择 y 的值要大，这样 min(A) <= y <= max(A) .此外，A 存在唯一的局部最小值或最小值范围(M(y) 是凸的)。

所以我们可以从在区间 [min(A) .. max(A)] 中选择一些 y 开始并尝试移动这个值，以便我们得到更小的 M(y)。为了让事情更容易理解，让我们对 A 进行排序并在 [1 .. n] 中选择一个 i (所以 y = A[i] )。

需要考虑三种情况。

如果A[i+1] > A[i] ，或者 {n 是奇数并且 i < (n+1)/2 } 或 {n 是偶数且 i < n/2 }, 然后 M(A[i+1]) < M(A[i]) .
这是因为，从 M(A[i])至 M(A[i+1]) ，减少的项数(即 n-i )大于增加的项数(即 i )，并且增加或减少的数量始终相同。在 n 为奇数的情况下，i < (n+1)/2 <=> 2*i < n+1 <=> 2*i < n ，因为 2*i 是偶数(因此必然小于我们从中减去一个的更大的偶数)。
用更正式的话来说，M(A[i]) = sum(A[i]-A[s]) + sum(A[g]-A[i]) ，其中 s 和 g 代表这样的索引 A[s] < A[i]和 A[g] > A[i] .所以如果A[i+1] > A[i] , 然后 M(A[i+1]) = sum(A[i]-A[s]) + i*(A[i+1]-A[i]) + sum(A[g]-A[i]) - (n-i)*(A[i+1]-A[i]) = M(A[i]) + (2*i-n)*(A[i+1]-A[i]) .自 2*i < n和 A[i+1] > A[i] , (2*i-n)*(A[i+1]-A[i]) < 0 , 所以 M(A[i+1]) < M(A[i]) .

类似地，如果A[i-1] < A[i] ，或者 {n 是奇数并且 i > (n+1)/2 } 或 {n 是偶数且 i > (n/2)+1 }, 然后 M(A[i-1]) > M(A[i]) .

最后，如果 {n 是奇数且 i = (n+1)/2 } 或 {n 是偶数且 i = (n/2) or (n/2)+1 }，那么你有一个最小值，因为递减或递增 i 最终将分别引导你到第一种或第二种情况。 i 有剩余的可能值，但所有这些都导致 A[i] 也是最小值。

A的中位数恰好是i满足最后一种情况的值A[i]。如果 A 中的元素个数是奇数，那么只有一个这样的值，y = A[(n+1)/2] (但可能有多个索引)；如果它是偶数，那么你有一个范围(可能只包含一个整数)这样的值，A[n/2] <= y <= A[n/2+1] .

有一个标准的 C++ 算法可以帮助您在 O(n) 时间内找到中位数:nth_element .如果您使用其他语言，请查找 the median of medians algorithm (Nico Schertler pointed out )甚至 introselect (这是 nth_element 通常使用的)。