我可以想到两种方法来解决它，尽管我的直觉告诉我，费舍尔·耶茨应该进行修改以更好地实现它：
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)。
现在，您将获得一棵新的二叉树，其权重已修改，并且可以选择下一个候选树，直到树被用尽。
