我可以想到两种方法来解决它，尽管我的直觉告诉我，费舍尔·耶茨应该进行修改以更好地实现它：

O（n * W）解决方案：（ 易于编程）

第一种方法，根据权重（与您的方法相同）创建重复项，然后填充新列表。现在，在此列表上运行标准混洗（fisher-
yates）。迭代列表并丢弃所有重复项，并仅保留每个元素的第一次出现。它在中运行O(n*W)，其中n是列表中元素的数量，并且W是平均权重（伪多项式解决方案）。

O（nlogn）解决方案：（ 非常难编程）

第二种方法是创建元素权重之和的列表：

sum[i] = weight[0] + ... + weight[i]

现在，在0到之间绘制一个数字，sum[n]并选择第一个元素，该元素sum大于/等于该随机数。
这将是下一个元素，丢弃该元素，重新创建列表，然后重复。

这在 O(n^2*logn)

通过创建二叉树而不是列表，可以进一步增强它，其中每个节点还存储整个子树的权重值。
现在，在选择一个元素之后，找到匹配的元素（其总和是第一个高于随机选择的数字的元素），删除该节点，然后重新计算到该路径的路径上的权重。
这将需要O(n)创建树，O(logn)在每个步骤中找到节点并O(logn)重新计算总和。重复此操作，直到树被用尽，然后您将获得O(nlogn)解决方案。
这种方法的思想与订单统计树非常相似，但使用权重之和而不是后代的数量。删除后的搜索和平衡将类似于统计树的排序。

构造和使用二叉树的说明。

假设你有elements=[a,b,c,d,e,f,g,h,i,j,k,l,m]与weights=[1,2,3,1,2,3,1,2,3,1,2,3,1]

首先构造一个几乎完整的二叉树，然后填充其中的元素。请注意，该树不是二进制搜索树，而只是常规树，因此元素的顺序无关紧要-以后我们将不需要对其进行维护。

您将获得类似以下树的内容：

图例： w-该节点的权重，sw-整个子树的权重之和。

接下来，计算每个子树的权重之和。从叶子开始，然后计算s.w = w。对于其他每个节点，请计算s.w = left->s.w + right->s.w，从下往上填充树（后遍历）。

在中完成构建树，填充树并s.w.为每个节点进行计算O(n)。

现在，您需要迭代地选择一个介于0与权重之和（在本例中为25的根的sw值）之间的随机数。将该数字设为r，并为每个这样的数字找到匹配的节点。
查找匹配的节点以递归方式完成

if `r< root.left.sw`:
   go to left son, and repeat. 
else if `r<root.left.sw + root.w`:
   the node you are seeking is the root, choose it. 
else:
   go to `root.right` with `r= r-root.left.sw - root.w`

例如，选择r=10：

Is r<root.left.sw? Yes. Recursively invoke with r=10,root=B (left child)
Is r<root.left.sw No. Is r < root.left.sw + root.w? No. Recursively invoke with r=10-6-2=2, and root=E (right chile)
Is r<root.left.sw? No. Is r < root.left.sw + root.w? Yes. Choose E as next node.

这是在O(h) = O(logn)每次迭代中完成的。

现在，您需要删除该节点，并重置树的权重。
确保树的对数权重的一种删除方法类似于二进制堆：用最右边的底部节点替换所选节点，删除最右边的新底部节点，并重新平衡从两个相关节点到树的两个分支。

第一开关：

然后重新计算：

请注意，只需要对两条路径进行重新计算，每个路径最多为深度O(logn)（图中的节点显示为橙色），因此删除和重新计算也是O(logn)。

现在，您将获得一棵新的二叉树，其权重已修改，并且可以选择下一个候选树，直到树被用尽。