java - 在java中生成半百万个唯一整数

Question

我希望在 1 到 100 万的范围内生成 500000 个唯一的随机整数。这些数字必须是唯一的，我希望它在 atleast 线性时间内并且不使用太多内存。有人可以想出解决方案吗？

Answer 1

作为was said以前，你可以打乱数字，拉出前半部分，这样它们就独一无二了。这是线性的，因为改组是 O(n)，而取第一部分是 O(n/2)。

Hare 是该线程的修改实现。这将打印 1-1m 范围内的 500k 个唯一随机数。

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

public class UniqueRandomNumbers {

public static void main(String[] args) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i=1; i<1000001; i++) {
        list.add(new Integer(i)); // adding all the numbers between 1-1m to a list.
    }
    Collections.shuffle(list); // using the built in shuffle function to make the unique order
    for (int i=0; i<500000; i++) {
        System.out.println(list.get(i)); // printing the first 500k. Replace this with whatever you want to do with those numbers. 
        //Notice - since it might take a while, it might be worth it to let the user know of the progress.
    }
}
}