Come lo vedi di usare due strutture dati?

Una tabella hash che usi solo per inserire i numeri e vedere se sono gia presenti e l'array per inserire i numeri appena generati.

la complessità per generare n numeri random è quasi O(n) come limite inferiore. Usi un po' più di memoria... però la performance dovresti comunque averla.