Создание полмиллиона уникальных целых чисел в java

Question

Я хочу создать 500000 уникальных случайных целых чисел в диапазоне от 1 до миллиона. Номера должны быть уникальными, и я хочу его в atleast линейного времени и без использования так много памяти. Может ли кто-нибудь подумать о решении?

Answer 1

Как и раньше, вы можете перетасовать цифры и вытащить первую половину, чтобы они были уникальными. Это линейно, так как перетасовка равна O(n), а первая часть - O(n/2).

Заявка является модифицированной реализацией этой темы. Это будет печатать 500k уникальных случайных чисел из диапазона 1-1m.

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. 
    } 
} 
} 

Answer 2

Если память на премию, использовать растровое изображение, чтобы вспомнить, какой из миллиона были выбраны, а затем повторно выбрать случайное число и остановка после 500.000. Это в основном оптимальное хранилище, так как lg (1e6 выбирает 0.5e6) не намного меньше 1e6.