将数组分为n个部分的算法 [英] Algorithms for dividing an array into n parts

问题描述

在最近一次校园Facebook采访中，我要求将一个数组分为3个相等的部分，以使每个数组中的总和大致等于sum / 3。

我的方法
1。排序数组
2。向上填充array [k]（k = 0）（array [k] <= sum / 3）
3。在增量k之后，对array [k]重复上述步骤。

有没有更好的算法，或者是NP难题？

In a recent campus Facebook interview i have asked to divide an array into 3 equal parts such that the sum in each array is roughly equal to sum/3.

My Approach
1. Sort The Array
2. Fill the array[k] (k=0) uptil (array[k]<=sum/3)
3. After that increment k and repeat the above step for array[k]

Is there any better algorithm for this or it is NP Hard Problem

推荐答案

这是分区问题的一种变体（请参见 http：//en.wikipedia .org / wiki / Partition_problem 了解详情）。实际上，对此的一种解决方案可以解决一个问题（采用一个数组，将其填充为0，然后解决此问题），因此此问题很难解决。

This is a variant of the partition problem (see http://en.wikipedia.org/wiki/Partition_problem for details). In fact a solution to this can solve that one (take an array, pad with 0s, and then solve this problem) so this problem is NP hard.

有一个伪多项式的动态规划方法。对于从 0 到数组大小的每个 i ，您将跟踪当前大小的所有可能组合子数组及其当前和。只要数组的子集总数有限，运行速度就可以接受。

There is a dynamic programming approach that is pseudo-polynomial. For each i from 0 to the size of the array, you keep track of all possible combinations of current sizes for the sub arrays, and their current sums. As long as there are a limited number possible sums of subsets of the array, this runs acceptably fast.

我建议的解决方案是为了好。足够的亲密关系。首先，让我们考虑一下所有值都是正数的简单问题。然后按降序排序。三分之二的阵列。通过始终将三元组中的最大数与总和最小的那个，最小的与最大的那个和中间的中间相加来构建三个子集。最后，您将均匀划分数组，其差将不超过第三个最小元素的值。

The solution that I would have suggested is to just go for "good enough" closeness. First let's consider the simpler problem with all values positive. Then sort by value descending. Take that array in threes. Build up the three subsets by always adding the largest of the triple to the one with the smallest sum, the smallest to the one with the largest, and the middle to the middle. You will end up dividing the array evenly, and the difference will be no more than the value of the third smallest element.

对于一般情况，您可以分为正数和负数，对每个负数使用上述方法，然后强行使用一组正数，一组负数以及中间的一些剩余值（未平均分配）的所有组合。

For the general case you can divide into positive and negative, use the above approach on each, and then brute force all combinations of a group of positives, a group of negatives, and the few leftover values in the middle that did not divide evenly.

这篇关于将数组分为n个部分的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！