0

I wish to generate 500000 unique random integers within range of 1 to a million. The numbers have to be unique and i want it in atleast linear time and without using so much memory. Can someone think of a solution ?

Hoshank Ailani
  • 21
  • 4
  • check this http://stackoverflow.com/questions/8115722/generating-unique-random-numbers-in-java – Radi Aug 20 '15 at 11:59

2 Answers2

1

As was said before, you can shuffle the numbers, and pull the first half so they'll be unique. This is linear, since shuffling is O(n), and taking the first part is O(n/2).

Hare is a modified implementation from that thread. This will print 500k unique random numbers from the range 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.
    }
}
}
Community
  • 1
  • 1
A. Abramov
  • 1,823
  • 17
  • 45
1

If memory is at a premium, use a bitmap to remember which of the million have been chosen, then repeatedly choose a random number and stop after 500,000. This is basically storage optimal, since lg(1e6 choose 0.5e6) is not much less than 1e6.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120