将数组分为n部分的算法

Question

在最近的校园Facebook面试中，我要求将一个数组分成3个相等的部分，使得每个数组中的总和大致等于sum/3。

我的方法
1.对数组进行排序
2.填充数组[k]（k = 0）uptil（array [k] < = sum/3）3.在此之后，递增k并重复上述步骤[k]

有没有更好的算法，或者是NP硬问题

Answer 1

这是分区问题的一个变种（详见http://en.wikipedia.org/wiki/Partition_problem）。事实上，解决这个问题可以解决这个问题（取一个数组，填充0，然后解决这个问题），所以这个问题很难。

有一个伪多项式的动态规划方法。对于从0开始的每个i到阵列的大小，您都会跟踪子阵列的当前大小的所有可能组合以及它们的当前总和。只要阵列的子集数量有限，这个运行速度可以接受得很快。

我会建议的解决方案是为了“足够好”的亲密度。首先让我们考虑所有值为正的简单问题。然后按值降序排序。三联阵容。建立三个子集，总是把三元组中最大的一个加到总和最小的那个，最小的到最大的一个，中间到中间。您将最终平均分配阵列，差异将不会超过第三个最小元素的值。

对于一般情况下，你可以分为积极和消极，每个使用上述方法，然后蛮力所有组合的一组积极，一组否定和中间的少数剩余值不均匀分配。

Answer 2

如果您有兴趣，以下是有关动态编程解决方案的详细信息。运行时间和内存使用量为O（n *（sum）^ 2），其中n是数组的大小，sum是数组值的绝对值之和。对于从1到n的每个数组索引j，当​​您将数组从索引1分割为3个子集时，存储所有可能的3个子集总和值。同样对于每种可能性，存储一种可能的方式来拆分数组以获得3个和。然后为了从1到j的信息将这个信息扩展到1到（j + 1），简单地把3个和的每个可能的组合分割成1到j，并形成3个和你选择添加（j + 1）个数组元素分配给3个子集中的任何一个。最后，当你完成并达到j = n时，当你将阵列位置1到n分成3组时，通过3个子集总和的所有组合的集合，并选择与sum/3的最大偏差为最小化。起初这可能看起来像O（n *（sum）^ 3）复杂度，但是对于每个j和前两个子集总和的每个组合，第三子集和是唯一确定的。 （因为你不允许忽略数组中的任何元素）。因此，复杂性实际上是O（n *（sum）^ 2）。