我知道这是一个非常老的问题，但是我认为，如果您应用一些数学运算，可以在O（n）时间内完成此操作！

该指数分布有两个非常有用的特性。

1. 给定来自具有不同速率参数的不同指数分布的n个样本，给定样本为最小值的概率等于其速率参数除以所有速率参数之和。

2. 这是“无记忆的”。因此，如果您已经知道最小值，那么其余元素中的第二个元素到第二个元素的概率与如果删除（并且从未生成）真正的最小值的概率相同，那么该元素将是新元素。分钟 这似乎很明显，但是我认为由于某些条件概率问题，其他分布可能不正确。

使用事实1，我们知道选择单个元素可以通过以下方法完成：生成速率参数等于权重的这些指数分布样本，然后选择最小值。

使用事实2，我们知道我们不必重新生成指数样本。相反，只需为每个元素生成一个，然后取k个元素的样本数最少即可。

可以在O（n）中找到最低的k。使用Quickselect算法找到的第k个元素，则简单地采取另一路经比第k个下的所有元素和输出所有。

一个有用的注意事项：如果您没有立即访问库以生成指数分布样本的方法，则可以通过以下方法轻松完成： -ln(rand())/weight