找到将阵列切成两半的位置,使得总和的差异最小

Question

我正在做一些练习编程问题以准备面试.

其中一个问题如下:您试图找到将阵列切成两半的位置,这样每个半部的总和之间的差异就会最小化.可以实现的最小差异是什么？

所以

A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3

我们可以在四个地方拆分这个磁带:

P = 1, difference = |3 ? 10| = 7 
P = 2, difference = |4 ? 9| = 5 
P = 3, difference = |6 ? 7| = 1 
P = 4, difference = |10 ? 3| = 7 

所以我们将返回1,因为这是最小的差异.

这很容易在n平方时间内完成,但是问题规定它可以在n个时间内完成,具有n个存储空间.有谁能推荐一个解决方案？我看待它的每一种方式,即使有额外的空间,你也必须继续沿阵列运行.在选择哪个切割最小之前,您需要知道整个数组的值.

Answer 1

通过两次O(n)通过可以找到中间切割位置.考虑一下你原来的问题

A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3

迭代这个值数组并在一个名为的新数组中记录增量和sums:

sums[0] = 3
sums[1] = 4
sums[2] = 6
sums[3] = 10
sums[4] = 13

在此迭代之后,您还知道总和是多少,在这种情况下是13.现在,所有你需要做的就是通过走sums阵列和选择哪个值最接近到一半的总和.在这种情况下,sums[2] = 6适合账单,所以你可以在第三个位置进行切割.

sums[0] = 3
sums[1] = 4
sums[2] = 6
-----------      <-- make the cut here
sums[3] = 10
sums[4] = 13