algorithm - 绝对值之和的最小值

Question

问题陈述:

有3个数组A,B,C，都是正整数，三个数组的大小都一样。

找到 min(|a-b|+|b-c|+|c-a|) 其中 a 在 A 中，b 在 B 中，c 在 C 中。

---

我整个周末都在研究这个问题。一个 friend 告诉我，可以在线性时间内完成。我不明白这怎么可能。

你会怎么做？

Answer 1

好吧，我想我可以在 O(n log n) 内完成。如果数组最初已排序，我只能执行 O(n)。

首先，观察您可以置换 a , b , c但是你喜欢而不改变表达式的值。所以让 x是最小的 a , b , c ;让 y成为三者的中间；让z是最大的。然后注意表达式正好等于 2*(z-x) . (编辑:这很容易看出......一旦你按顺序排列了三个数字，x < y < z，总和就是(y-x) + (z-y) + (z-x)，等于2*(z-x))

因此，我们真正要做的就是找到三个数字，使最外面的两个数字尽可能靠近，另一个数字“夹在”它们之间。

所以首先在 O(n log n) 中对所有三个数组进行排序。维护每个数组的索引；称这些为i , j , 和 k .将所有三个初始化为零。无论哪个索引指向最小值，都增加该索引。也就是说，如果 A[i]小于 B[j]和 C[k] , 递增 i ;如果B[j]最小，递增j ;如果C[k]最小，递增 k。重复，跟踪 |A[i]-B[j]| + |B[j]-C[k]| + |C[k]-A[i]|整个时间。您在这次行军中观察到的最小值就是您的答案。 (当三个中最小的一个在它的数组末尾时，停止，因为你已经完成了。)

在每一步中，您只对一个索引加一；但你只能这样做n在到达终点之前每个阵列的时间。所以这最多是3*n步骤，即 O(n)，小于 O(n log n)，意味着总时间为 O(n log n)。 (或者如果您可以假设数组已排序，则只需 O(n)。)

这有效的证明草图:假设 A[I] , B[J] , C[K]是 a , b , c形成实际答案；即，它们具有最小值 |a-b|+|b-c|+|c-a| .进一步假设 a > b > c ;其他情况的证明是对称的。

引理:在我们行进期间，我们不增加 j过去J直到我们递增 k 之后过去K .证明:我们总是增加最小元素的索引，并且当k <= K , B[J] > C[k] .所以当j=J和 k <= K , B[j]不是最小的元素，所以我们不增加 j .

现在假设我们递增 k过去K之前i达到 I .在我们执行该增量之前，情况是什么样的？嗯，C[k]在那一刻是三个中最小的，因为我们即将增加 k . A[i]小于或等于 A[I] ，因为 i < I和 A已排序。最后，j <= J因为k <= K (通过我们的引理)，所以 B[j]也小于A[I] .综合起来，这意味着此时我们的绝对差异之和小于 2*(c-a) ，这是矛盾的。

因此，我们不增加 k过去K直到 i达到 I .因此，在我们行军期间的某个时刻i=I和 k=K .通过我们的引理，此时j小于或等于 J .所以在这一点上，B[j]小于其他两个和j会增加；或 B[j]在另外两个之间，我们的总和就是2*(A[i]-C[k]) ，这是正确的答案。

这个证明很草率；特别是，它没有明确说明 a 中的一个或多个的情况。 , b , c是平等的。但我认为这个细节很容易解决。