小编tim*_*xyz的帖子

考虑一个问题,其中必须从X中选择k个项目的随机子列表Y,n个项目的列表,其中Y中的项目必须以与它们在X中相同的顺序出现.Y中的所选项目不必是不同.一个解决方案是:

for i = 1 to k
    A[i] = floor(rand * n) + 1
    Y[i] = X[A[i]]
sort Y according to the ordering of A

但是,由于排序操作,它具有运行时间O(k log k).要删除它,它很诱人

high_index = n
for i = 1 to k
    index = floor(rand * high_index) + 1
    Y[k - i + 1] = X[index]
    high_index = index

但由于统一的索引选择,这给返回列表提供了明显的偏差.如果第二溶液中的指数非均匀分布,则感觉可以获得O(k)溶液.有没有人知道是否是这种情况,如果是这样,边际指数的分布具有哪些属性？