將數組分爲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）。