绝对值之和的最小值

绝对值之和的最小值

好吧，我想我可以在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

过去。在执行该增量之前，情况如何？好吧，那是那时三者中最小的，因为我们将要增加。
小于或等于，因为和已排序。最后，因为（由我们的引理），所以也小于。总之，这意味着我们在这一刻总和法ABS-DIFF是 少
比，这是一个矛盾。

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

是相等的。但是我认为可以很容易地得出细节。