algorithm - 对受约束的排序列表进行分区

Question

这里是问题:

给定一个排序的整数列表(你可以假设它们是正的，如果它使问题更简单)，将列表分成'n'个相等大小的分区(或尽可能相等)，服从约束没有一个整数出现超过一个这样的分区。

约束本质上意味着如果你有一个列表{1,1,2,2}

那么所有的都必须在同一个集合中，所有的 2 必须在同一个集合中。所有 1 和所有 2 也可以在一组中。但是我们不能在第一个分区中有一个 1，在第二个分区中有第二个 1。

示例 1:



<pre><code> List: {1,1,2,2,3,3,4,4}


Number of partitions to make: 4

Answer: {1,1} {2,2} {3,3} {4,4}
</code></pre>

<p><strong>Example 2: (trickier one)</strong>
</p>



List: {1,1,2,2,2,3,3,4,4,4,4,4,4,4,4} 

Number of partitions to make : 3

Answer: {1,1,2,2} {3,3} {4,4,4,4,4,4,4,4}

    OR: {1,1} {2,2,3,3} {4,4,4,4,4,4,4,4}

注意这里第 3 个分区的大小必须为 8，因为由于限制，所有 4 个分区都必须在同一个分区中。

还有许多其他棘手的情况。如果有人需要更多示例，请告诉我。

那么问题是解决或解决这个问题的最佳方法是什么？

Answer 1

我能想到的最简单的解决方案是，

1. 首先在列表中找到所有相同的元素(如果您事先知道范围，请使用散列之类的方法找到它们或使用计数排序)并保持它们的大小。

2. 现在您将拥有一组重复数字(例如 {1,1} {2,2})。在这一步之后，尝试找到你拥有的列表的数量并将它们分组以形成 n 个分区(如问题陈述中所指定)。对于前。在你最后一个棘手的例子中，我们最终会有 4 个列表，你需要 3 个分区。您可以找到 2 个小列表并将它们组合成 1 个，重复此操作直到达到所需的分区数。