在Java中生成一定范围内的多个随机数，但有一些例外情况。

Question

我需要在一定范围内生成很多随机数，但有一些例外。目前我的计划是按照以下方式进行：

public class Main
{
    static List<Integer> except = Arrays.asList(5, 6, 11, 12, 17, 18, 23, 25, 28, 29);
    
    
    public static void main(String[] args) {
        
        List<Integer> randomNums = new ArrayList<>();
        
        Random random = new Random();
        
        int z;
        for(i=0; i<20; i++) {
            z = random.nextInt(30);
            while(except.contains(z)) z = random.nextInt(30);

            randomNums.add(z);
        }           
        
        System.out.println(randomNums);
    }
}

在我的情况中，“except”和“randomNums”的大小会更大。所以，代码将花费更多的时间在while循环中来避免我不想要的数字。

我很好奇是否可以加速我的代码？如果我能够移除while循环，那么它肯定就是O(n)。但是我该如何做到这一点呢？ 谢谢。

- abhimanyue

---

在except中使用Set而不是List。这样，contains()方法的时间复杂度将从O(n)变为O(1)。 - vanje

据我所知，无法删除while循环！ - K. Smith

我在思考，如果我可以使用某种映射从“随机数”-->“我需要的数字（不包括except中的数字）”，那么我就可以去掉while循环。@K. Smith - abhimanyue

你的随机数范围是变化的还是恒定的？ - Sebphil

你可以创建一个可接受数字的列表，然后使用随机生成器从该列表中获取给定位置的数字，但是我不知道这有多有用，因为你必须在开始时生成此列表。 - K. Smith

范围不是固定的，但我可以处理，我不打算自己生成随机数，可能使用有效的映射可以解决我的问题。 - abhimanyue

Answer 1

我的建议是您制作一个想要在结果中出现的所有数字列表，并每次从该列表中随机选择一个成员。这需要一些初始化，但之后您的循环应该会运行得很快。

    int maxExclusive = 30;
    Integer[] baseArr = new Integer[maxExclusive];
    Arrays.setAll(baseArr, Integer::valueOf);
    List<Integer> base = new ArrayList<>(Arrays.asList(baseArr));
    base.removeAll(except);
    
    List<Integer> randomNums = new ArrayList<>();
    
    Random random = new Random();
    
    for (int i = 0; i < 20; i++) {
        Integer z = base.get(random.nextInt(base.size()));
        randomNums.add(z);
    }
    
    System.out.println(randomNums);

示例输出：

[1、10、27、2、24、22、7、8、0、27、19、27、15、14、21、22、13、24、2、13]

这是一个包含整数的列表，每个整数之间用逗号分隔。

- Ole V.V.

---

@abhimanyue 顺便说一下，如果您不想要专业列表的重复项，可以使用 Collections.shuffle 并按顺序从列表中取出它们。 - WJS

Answer 2

这里有一种方法：

    public static void main(String[] args) {

        final int exceptMin = 5;
        final int exceptMax = 29;

        Set<Integer> except = new HashSet<>(
                Arrays.asList(5, 6, 11, 12, 17, 18, 23, 25, 28, 29)
        );

        List<Integer> safeValues = getSafeValues(except, exceptMin, exceptMax);

        List<Integer> randomValues = getRandomValues(except, safeValues);
    }

    public static List<Integer> getSafeValues(Set<Integer> except, int exceptMin, int exceptMax) {

        List<Integer> safeValues = new ArrayList<>();
        for(int i = exceptMin; i < exceptMax; i++) {

            if(!except.contains(i))
                safeValues.add(i);
        }

        return safeValues;
    }

    public static List<Integer> getRandomValues(Set<Integer> except, List<Integer> safeValues) {

        List<Integer> randomValues = new ArrayList<>();
        for(int i = 0; i < 800_0000; i++) {
            int randomNumber = getRandomValue(except, safeValues);
            randomValues.add(randomNumber);
        }

        return randomValues;
    }

    public static int getRandomValue(Set<Integer> except, List<Integer> safeValues) {

        ThreadLocalRandom  random = ThreadLocalRandom.current();

        int randomNumber = random.nextInt(0, 30);

        if(except.contains(randomNumber)) {
            int randomIndex = random.nextInt(safeValues.size());
            randomNumber = safeValues.get(randomIndex);
        }

        return randomNumber;
    }

所以，只需使用另一个列表来存储可以安全使用的值，并在随机生成的值失败时选择其中之一。正如 @vanje 已经提到的那样，它使用 HashSet 来执行查找，因为它对此具有常数时间复杂度 (https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html)。

这种方法在我的机器上的表现如下：

generated Numbers  time in ms
800_000            300
400_000            156
200_000            87
100_000            38

我使用了你提供的异常并生成了0（包括）到30（不包括）之间的数字，因此有很多“未命中”的情况。

然而，这种方法将比生成“新鲜”的随机值更耗费内存，并且需要一些准备工作。例如，当异常为{0, 100_0000}时，您将生成大量“安全”数字。您可以将safeNumbers列表分成多个列表来处理这个问题。 除此之外，如果您关心随机数的分布，这种方法可能会破坏您的随机数分布。

编辑：当我写这篇答案时，我没有意识到@Ole V.V.也使用了这种方法。如果需要，我会删除这篇答案。

- Sebphil

---

我建议你可以在这里留下答案。一方面，有些人可能会发现你的时间测量很有趣。另外，使用HashSet可能被认为是对我的代码的改进。 - Ole V.V.