4

在一次采访中，我被要求编写一个方法，该方法每次调用时都会生成唯一的 5 位随机数。例如：如果我调用该方法并得到 22222，那么在下一次调用中我不应该得到 22222。

我写了如下代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class RandomNumberGen {


    private static ArrayList arr=new ArrayList();
    private static int k=-1;
    public RandomNumberGen(){
        for (int i=10000;i<99999;i++){
            arr.add(i);
        }
        Collections.shuffle(arr);
    }
    public static void main(String[] args) {
        for(int m=0;m<10;m++){
            try {
                System.out.println(new RandomNumberGen().randomNumbermethod());
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }


    }
    public Integer randomNumbermethod() throws Exception{
        k++;
        if(k>=arr.size()){
            throw new Exception("No more number available");
        }else return (Integer) arr.get(k);
    }

}

答案被接受了，但我被要求现在避免内存浪费。我的问题在这里，你可以看到我只使用了 10 个数字。所以 arraylist 占用的其余空间是内存浪费。有没有一种方法可以在不使用额外内存的情况下实现相同的目标。我的意思是，在每次调用时都可以使用哪个唯一编号，这样就不会浪费这么多内存。

4

5 回答 5

7 
private static int number = 10000;
public int getNextUniqueRandomNumber() {
   return number++;
}

随机数发生器

于 2013-09-25T13:04:23.337 回答
7

影响：

  • 为了不返回相同的值两次，您需要跟踪您已经生成了哪些数字。这可能非常消耗内存。
  • 你最终会用完数字。您无需继续搜索未使用的随机数，而是可以跟踪您返回了多少个数字（或仍有多少个可用）并识别您是否用完了数字。

生成的数字可以在集合（Set）中进行跟踪。这意味着每个号码有 32 位的开销（在跟踪可用或生成的号码时）加上收集开销。另一种可能性是使用布尔数组并标记已使用的插槽。同样，这是一个开销，因为布尔值通常存储为 32 位值。
但是有一种更便宜的方式来存储布尔值：作为整数中的压缩位。就是java.util.BitSet这样，所以每个布尔值将占用一位。

解决方案BitSet并跟踪有多少可用号码：

public class RandomNumbers {

    private final Random random = new Random();
    private final BitSet used = new BitSet();
    private final int min = 10000;
    private final int max = 99999;
    private final int numbersAvailable = max - min + 1;

    public static void main (String[] args) {

        RandomNumbers randomNumbers = new RandomNumbers();
        for (int i = 0; i < 100; i++) {
            System.out.println(randomNumbers.nextRandom());
        }
    }

    public int nextRandom () throws NoSuchElementException {

        while (numbersAvailable > 0) {
            int rnd = min + random.nextInt(max - min + 1);
            if (!used.get(rnd)) {
                used.set(rnd);
                numbersAvailable--;
                return rnd;
            }
        }
        throw new NoSuchElementException();
    }
}
于 2013-09-25T13:08:44.207 回答
5

只是

(int)(Math.random()*89999)+10000

编辑后：（只是在编辑之前不理解）-您可以将生成的数字放入HashSet随机数之后，只需检查集合是否包含新数字（如果您多次使用它会很慢，但我认为这是一个很好的解决方案，如果您不需要很多数字。

根据我的评论：在超过大约 50% 的数字后，我会创建一个剩余数字的集合来选择，和你的一样，但是你应该在课堂上记录，它可以在 50% 的结果使用后冻结片刻并提供设置的能力这个因素给客户。

也许有更好的方法，取决于生成的数字中必须有“多少随机性”（例如序列生成器的数学方法）

于 2013-09-25T12:28:26.863 回答
4

看起来很简单。一个更简单且内存使用量更少的解决方案是创建一个集合来保存您想要的所有数字，如下所示：

Random random = new Random();
Set<Integer> randomNumbers = new HashSet<Integer>(10);
while(randomNumbers.size() < 10)
    randomNumbers.add( new Integer(random.nextInt(89999) + 10000) );

并查看所有内容：

for(Integer randomNumber : randomNumbers){
    System.out.println(randomNumber);
}

这将保证集合属性的唯一性，并大大提高您的内存使用率。

于 2013-09-25T12:47:08.257 回答
2

您的方法确实是创建大量唯一值的理想选择，但是如果您只创建少量唯一值，那么简单地跟踪使用的值以保证唯一性会更有效

import java.util.Collection;
import java.util.HashSet;
import java.util.Random;

public class UniqueRandom {

    static Random rnd=new Random();
    
    public static void main(String args[]){
        Collection<Integer> alreadyChosen = new HashSet<Integer>();
        for(int i=0;i<10;i++){
            System.out.println(getNextUniqueRandom (alreadyChosen));
        }
    }
    
    
    public static int getNextUniqueRandom(Collection<Integer> alreadyChosen){
        if (alreadyChosen.size()==90000){ //hardcoded 5 figure numbers, consider making a variable
             throw new RuntimeException("All 5 figure IDs used");
        }


        boolean unique=false;
        int value=0;
        while(unique==false){
            value=rnd.nextInt(90000)+10000;
            unique=!alreadyChosen.contains(value);
        }
        alreadyChosen.add(value);
        return value;
    }
    
}

当只需要一小部分可用范围时，这种方法非常有效，但随着碰撞变得越来越普遍，这种方法变得越来越慢。您应该选择的确切实现在很大程度上取决于您需要获得多少值。

需要考虑的注意事项

  • 如前所述，随着选择更多值，这将变得非常非常慢，应该让最终用户清楚，甚至更好；多次调用后更改算法
于 2013-09-25T12:41:53.923 回答