algorithm - 随机选择一组不同整数的最有效方法

Question

我正在寻找最有效的算法来随机选择一组 n 个不同的整数，其中所有整数都在某个范围 [0..maxValue] 内。

约束:

• maxValue 大于 n，并且可能大得多
• 我不关心输出列表是否排序
• 必须以相等的概率选择所有整数

我最初的想法是构建一个整数列表 [0..maxValue] 然后随机提取 n 个元素而不进行替换。但这似乎效率很低，尤其是当 maxValue 很大时。

有更好的解决方案吗？

Answer 1

这是一个最优算法，假设我们被允许使用 hashmaps。它在O(n) 时间和空间 中运行(而不是 O(maxValue) 时间，这太昂贵了)。

它基于弗洛伊德的随机样本算法。看我的blog post关于它的详细信息。代码在 Java 中:

private static Random rnd = new Random();

public static Set<Integer> randomSample(int max, int n) {
    HashSet<Integer> res = new HashSet<Integer>(n);
    int count = max + 1;
    for (int i = count - n; i < count; i++) {
        Integer item = rnd.nextInt(i + 1);
        if (res.contains(item))
            res.add(i);
        else
            res.add(item);
    }
    return res;
}