问题陈述：

有3阵列A，B，C都填充有正整数，并且所有的三个阵列的大小相同的

There are 3 arrays A,B,C all filled with positive integers, and all the three arrays are of the same size.

查找分钟（| AB | + | BC | + | CA |），其中一个是A，B是B，C是在C

Find min(|a-b|+|b-c|+|c-a|) where a is in A, b is in B, c is in C.

我的工作问题了整个周末。一个朋友告诉我，它可以在线性时间内完成。我看不出这是可能的。

I worked on the problem the whole weekend. A friend told me that it can be done in linear time. I don't see how that could be possible.

你会怎么做呢？

推荐答案

嗯，我想我可以做到这一点在为O（n log n）的。我只能做O（N），如果阵列最初排序。

Well, I think I can do it in O(n log n). I can only do O(n) if the arrays are initially sorted.

首先，请注意，您可以重排 A ， B ， C 但是你喜欢不改变原pression值。因此，让 X 是最小的 A ， B 中， C ;让是是三者的中间;让以Z 为最大。然后注意的是，前pression只是等于 2 *（ZX）。 （编辑：这是很容易看到。一旦你有三个数字的顺序， X＆LT; Y＆LT; Z ，总和就是（YX）+（ZY）+（ZX）等于 2 *（ZX））

First, observe that you can permute a,b,c however you like without changing the value of the expression. So let x be the smallest of a,b,c; let y be the middle of the three; and let z be the maximum. Then note that the expression just equals 2*(z-x). ( This is easy to see... Once you have the three numbers in order, x < y < z, the sum is just (y-x) + (z-y) + (z-x) which equals 2*(z-x))

因此​​，我们所真正想要做的是找到三个数字，使得外部两者的紧密越好，与其他一些它们之间的夹心。

Thus, all we are really trying to do is find three numbers such that the outer two are as close together as possible, with the other number "sandwiched" between them.

因此​​，通过O型三种阵列（N log n）的排序开始。保持一个指数到每个阵列;把这些我，Ĵ和 K 。初始化所有三到零。取其索引点到最小的值，递增该索引。也就是说，如果 A [1] 比 B [J] 和 C [小K] ，增量我;如果 B [J] 最小，增量Ĵ;如果 C [K] 最小，增量ķ。重复，跟踪的| A [1] -B [J]。| + | B [J] -C [K] | + | C [K] -A [我] | 的全部时间。你这个行军途中观察到的最小值就是你的答案。 （当三者中最小的是在它的数组的末尾，停下来，因为你做。）

So start by sorting all three arrays in O(n log n). Maintain an index into each array; call these i, j, and k. Initialize all three to zero. Whichever index points to the smallest value, increment that index. That is, if A[i] is smaller than B[j] and C[k], increment i; if B[j] is smallest, increment j; if C[k] is smallest, increment k. Repeat, keeping track of |A[i]-B[j]| + |B[j]-C[k]| + |C[k]-A[i]| the whole time. The smallest value you observe during this march is your answer. (When the smallest of the three is at the end of its array, stop because you are done.)

在每个步骤中，您将添加一个只有一个指标;但你只能打在年底前做到这一点 N 次，每次阵列。所以这是最 3 * N 步骤，这是O（n），小于为O（n log n）的，这意味着总时间为O（n日志N）。 （或者只是为O（n），如果你可以假设数组排序。）

At each step, you add one to exactly one index; but you can only do this n times for each array before hitting the end. So this is at most 3*n steps, which is O(n), which is less than O(n log n), meaning the total time is O(n log n). (Or just O(n) if you can assume the arrays are sorted.)

一个证明，这个工程的素描：假设 A [1] ， B [J] ， C [K] 是 A ， B ， C ，形成了实际的答案;也就是说，他们有最低 | AB | + | BC | + | CA | 。进一步假设 A > B > C ;证明对于其他情况下是对称的。

Sketch of a proof that this works: Suppose A[I], B[J], C[K] are the a, b, c that form the actual answer; i.e., they have the minimum |a-b|+|b-c|+|c-a|. Suppose further that a > b > c; the proof for the other cases is symmetric.

引理：在我们的3月，我们不会增加Ĵ过去Ĵ，直到我们增加后的 K 过去 K 。证明：我们总是递增最小元素的索引，而当 K＆LT; = K ， B [J] GT; C [K] 。因此，当当J = J 和 K＆LT; = K ， B [J] 不是最小的元素，所以我们不会增加Ĵ。

Lemma: During our march, we do not increment j past J until after we increment k past K. Proof: We always increment the index of the smallest element, and when k <= K, B[J] > C[k]. So when j=J and k <= K, B[j] is not the smallest element, so we do not increment j.

现在假设我们增加 K 过去 K 在我达到我。什么东西的样子做就在我们执行的增量？好了， C [K] 是三者中最小的那一刻，因为我们将要增加 K 。 A [1] 小于或等于 A [1] ，因为 I＆LT ;我和 A 进行排序。最后， J＆LT; = j的，因为 K＆LT; = K （我们引理），因此 B [J] 比 A [1] 。总之，这意味着我们的加总-ABS的-DIFF此时此刻的少的比 2 *（CA），这是一个矛盾。

Now suppose we increment k past K before i reaches I. What do things look like just before we perform that increment? Well, C[k] is the smallest of the three at that moment, because we are about to increment k. A[i] is less than or equal to A[I], because i < I and A is sorted. Finally, j <= J because k <= K (by our Lemma), so B[j] is also less than A[I]. Taken together, this means our sum-of-abs-diff at this moment is less than 2*(c-a), which is a contradiction.

因此​​，我们不会增加 K 过去 K 直到我达到我。因此，在我们的行军中的某些点 I = I 和 K = K 。根据我们的引理，在这一点上Ĵ小于或等于Ĵ。所以在这一点上，无论是 B [J] 小于其他两个和Ĵ将得到增加;或 B [J] 是其他两者之间，我们的总和就是 2 *（A [1] -C [K]），这是正确的答案。

Thus, we do not increment k past K until i reaches I. Therefore, at some point during our march i=I and k=K. By our Lemma, at this point j is less than or equal to J. So at this point, either B[j] is less than the other two and j will get incremented; or B[j] is between the other two and our sum is just 2*(A[i]-C[k]), which is the right answer.

这证明是草率的;特别是，它没有明确解释的情况下，一个或多个 A ， B ， C 相等。但我认为，细节可以很容易地计算出pretty的。

This proof is sloppy; in particular, it fails to explicitly account for the case where one or more of a,b,c are equal. But I think that detail can be worked out pretty easily.