gpt4 book ai didi

arrays - 找到将数组切成两半的位置,使得总和的差异最小

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:29:26 24 4
gpt4 key购买 nike

我正在做一些编程练习题来准备面试。

其中一个问题如下:您试图找到将数组切成两半的位置,以使每一半之和之间的差异最小化。可以实现的最小差异是多少?

所以

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 个存储空间。任何人都可以推荐一个解决方案吗?我以任何方式看待它,即使有额外的空间,你也必须继续沿着阵列运行。您需要知道整个数组的值,然后才能选择最小的切割。

最佳答案

通过两次 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

关于arrays - 找到将数组切成两半的位置,使得总和的差异最小,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32084734/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com