Java: Duplikate einer Zufallszahl in Array finden und ersetzen.

Question

Aufgabe:

Grundsätzlich geht es um Zeitkomplexität, daher muss selber ein Algorithmus geschrieben werden, der nacheinander für die Indizes eines Arrays (also 0 bis size-1) eine Zufallszahl von 1 bis size erzeugt.

Ist die erzeugte Zufallszahl aber schon im Array enthalten, soll sie verworfen und neu generiert werden.


Problem/Ansatz:

Mein Problem ist eigentlich wie folgt (mein Java ist nicht so gut, wie meine Note es aussagt ;) ):

Ich habe mehrere Ansätze ausprobiert, aber scheiter gerade an folgendem Problem. Wenn ich über das Array iteriere, prüfe ich ob die generierte Zufallszahl im Array enthalten ist, findet er ein Duplikat, wird die Zahl neu generiert, aber weiter über das Array iteriert, heißt eine Zufallszahl die schon vorher vorgekommen ist, kann erneut vorkommen.

Leider stehe ich hier etwas auf dem Schlauch und es ist wahrscheinlich recht trivial.

int[] a = new int[size]; 

for(int i=0; i<a.length; i++) { 
    int rnd = (int)(1+Math.random()*(size-1)); 
      for(int j=0; j<a.length; j++) { 
        if(a[j] == rnd) { 
        rnd = (int)(1+Math.random()*(size-1)); 
        } else { 
        a[i] = rnd; 
      } 
    } 
} 

Update:

Okay, noch ein bisschen weiter gemacht, neuer Code mit deutlich besserem Ergebnis:

int[] a = new int[size];
        
      for (int i = 0; i < a.length;  ++i) {
      a[0] = (int)(1+Math.random()*(size-1));
            for (int j = 0; j < i; j++) {
                if (a[j] == a[i]) {
                    a[i] = (int)(1+Math.random()*(size));
                    j = 0;
                } 
            }
        }

Das Problem ist in diesem Fall eher, das der Check für die Zahl im Index 0 nicht richtig funktioniert.

Answer 1

int[] a = new int[size]; 

for(int i=0; i<a.length; i++) { 
    bool unique;
    do {
        int rnd = (int)(1+Math.random()*(size-1)); 
        unique = true;
        for(int j=0; j < i; j++) { 
            if(a[j] == rnd) { 
                unique = false;
                break;
            }
        }
        if (unique) {
            a[i] = rnd;
        }
    } while (!unique);
} 

Die Zeitkomplexität ist katastrophal.