小编典典

将N个列表中的项组合成具有均衡分布的项的好的算法?

algorithm

假设我有以下三个列表

A1
A2
A3

B1
B2

C1
C2
C3
C4
C5

我想将它们合并到一个列表中,每个列表中的项目都尽可能均匀地分配,如下所示:

C1
A1
C2
B1
C3
A2
C4
B2
A3
C5

我正在使用.NET 3.5 / C#,但我正在寻找更多方法以及特定代码。

编辑:我需要保留原始列表中元素的顺序。


阅读 237

收藏
2020-07-28

共1个答案

小编典典

  1. 获取成员最多的列表副本。这将是目的地列表。

  2. 然后从列表中选择倒数第二个。

  3. 将目标列表长度除以较小的长度,以得到大于1的分数。

  4. 对于第二个列表中的每个项目,请维护一个浮动计数器。将上一步中计算出的值相加,然后在数学上将其四舍五入为最接近的整数(保持原始浮点计数器不变)。将其插入目的地列表中的此位置,并将计数器加1即可解决。对第二个列表中的所有列表成员重复此操作。

  5. 对所有列表重复步骤2-5。

编辑:这也有作为O(n)的优势,这总是很好:)

2020-07-28