在数组中查找平衡点

Question

这个问题来自一个很棒的youtube频道,提出了可以在访谈中提出的问题.

它基本上与在阵列中找到平衡点有关.这是一个最好地解释它的例子; {1,2,9,4,-1}.在这里,因为sum(1 + 2)= sum(4 +( - 1)),使得9为平衡点.在没有检查答案的情况下,我决定在想要询问是否可以采用更有效的方法之前实施算法;

1. 求和数组O(n)中的所有元素
2. 得到一半的总和O(1)
3. 从左开始扫描阵列,并在sumleft大于一般总和的一半时停止.上)
4. 做同样的权利,获得总和权利. O(n).
5. 如果sumleft等于sumright return arr [size/2],则返回-1

我问,因为这个解决方案毫不费力地突然出现,提供了O(n)运行时间.这个解决方案,如果是真的,可以开发,或者如果不是真的任何替代方法？

Answer 1

你的算法是不好的(反例:1 -1 1 0 1 -1 1),很好的解决方案是计算你的阵列的部分和(这样就可以可以计算sumleft并sumright在O(1)对数组的每个单元格),然后(或在同一时间,如果你已经知道全局和)在你的数组中搜索一个单元格,那sumleft = sumright就是O(n).

数组的部分和A是

[A[0], A[0]+A[1], A[0]+A[1]+A[2], …, A[0]+A[1]+A[2]+…+A[n-1]]

例:

A=[5,2,3,1,4,6]
partial sum = [5,7,10,11,15,21]

有了这个数组,你可以计算sumleft[i]=partial_sum[i-1]和sumright[i]=partial_sum[n-1]-partial_sum[i]

改进:

如果存储所有partial_sum数组,则首先计算全局和,然后仅计算当前索引的部分和,这样就可以仅使用O(1)额外空间而不是O(n)额外空间.