从Java BitSet中随机选取n个k位

Question

如何挑选恰好k从一个位的Java位集合的长度m与n位打开,在那里k?n?m？

输入示例: m=20, n=11

示例输出: k=3

天真的做法

选择一个随机数.0? i ? m-1如果它在输入上打开而未在输出上打开,则在输出中将其k打开,直到在输出中打开位.

当n比小得多时,这种方法会失败m.还有其他想法吗？

Answer 1

您可以从第一位扫描到最后一位,并将储存采样应用于设置的位.

该算法具有O(m)时间复杂性,并且需要O(k)存储器.