Suche nach fehlenden ganzen Zahlen in einem sortierten Array

Question

Ich musste die fehlenden ganzen Zahlen (zufällig erzeugt im Bereich von 0-9) in einem Array mit der Länge = 10 finden. Ich hatte die Idee, das Array zu sortieren und dann für jedes Array zu überprüfen wenn es der Position im Array entspricht. Ich kam mit dem folgenden Code auf:

public void nichtGetroffen(){ 
    s.quickSort(enten, 0, enten.length -1); 
    sum = 0; 
    for (int i=0; i < enten.length; i++){ 
     if(enten[i] != i){ 
      System.out.print(i + ""); 
      sum = sum +1; 
     } 
    } 

Das Problem ist, dass es manchmal und manchmal funktioniert es nicht und ich leider keine Ahnung, wie diese zu lösen. (Enten ist der Name des Arrays)

Answer 1

Wenn Sie das Array sortieren, wenn das nächste Element mehr als 1 größer als das aktuelle Element ist, haben Sie fehlende Zahlen. Suchen Sie dann nach fehlenden Zahlen am Anfang und Ende des Arrays.

s.quickSort(enten, 0, enten.length -1); 

// Print missing numbers less than the smallest element. 
for (int j = 0; j < enten[0]; ++j) { 
    System.out.println(j); 
} 

// Print missing numbers between elements. 
for (int i = 1; i < enten.length; ++i) { 
    // If enten[i - 1] + 1 >= enten[i], this loop body never runs. 
    for (int j = enten[i - 1] + 1; j < enten[i]; ++j) { 
    System.out.println(j); 
    } 
} 

// Print missing numbers greater than the largest element. 
for (int j = enten[enten.length-1] + 1; j <= 9; ++j) { 
    System.out.println(j); 
} 

Answer 2

Wenn ich understend gut Ihre Frage haben, füllen Sie ein set Sammlung mit dem Array Sie bekam und dann überprüfen die Länge ist gleich zu 10.

HashSet<Integer> set = new HashSet<>(arrayOfRandomNumbers); 
if (set.size() == 10) { 
    //all elements in array 
} 

Answer 3

Eine Möglichkeit, dies zu tun, es so verwenden Set und seine Eigenschaft, nur einen einzigartigen Elementen:

public static void main(String[] args) { 
    // randomizing 
    int nMin = 5; 
    int nMax = 50; 
    int x = 20; 
    Random r = new Random(); 
    Integer[] arr = new Integer[x]; 
    for (int i = 0; i < x; i++) { 
     int val = nMin + r.nextInt(nMax - nMin); 
     System.out.println(val); 
     arr[i] = val; 
    } 

    // detection 

    Set<Integer> set = new HashSet<Integer>(Arrays.asList(arr)); 
    List<Integer> missing = new ArrayList<>(); 
    for (int i = nMin; i < nMax; i++) { 
     if (!set.contains(i)) { 
      missing.add(i); 
     } 
    } 

    System.out.println("Missing elements count " + missing.size()); 
    System.out.println("Missing elements: " + missing.toString()); 
} 

Dieses Sie die fehlenden interegs aus dem Satz von X (20) alle Zufallszahlen zwischen nMin geben (5) und nMax (50) einschließlich;

Answer 4

ist die komplette Lösung für Ihre „originäre Aufgabe“ Sie im Kommentar erwähnt:

public class Gaps { 
    public static void main(String[] args) { 
     int runs = 100; 
     int nMin = 0; 
     int nMax = 10; 
     int x = 10; 

     double missingSum = 0; 

     for (int run = 0; run < runs; run++) { 
      Integer[] arr = randomize(nMin, nMax, x); 
      List<Integer> missing = getMissingElements(nMin, nMax, arr); 
      missingSum += missing.size(); 
     } 
     double avg = missingSum/runs; 
     System.out.println("Missing elements avarage count: " + avg); 

    } 

    private static List<Integer> getMissingElements(int nMin, int nMax, Integer[] arr) { 
     Set<Integer> set = new HashSet<Integer>(Arrays.asList(arr)); 
     List<Integer> missing = new ArrayList<>(); 
     for (int i = nMin; i < nMax; i++) { 
      if (!set.contains(i)) { 
       missing.add(i); 
      } 
     } 
     return missing; 
    } 

    private static Integer[] randomize(int nMin, int nMax, int x) { 
     Random r = new Random(); 
     Integer[] arr = new Integer[x]; 
     for (int i = 0; i < x; i++) { 
      int val = nMin + r.nextInt(nMax - nMin); 
      arr[i] = val; 
     } 
     return arr; 
    } 

} 

Answer 5

Hier ist ein Beispiel dafür, warum es nicht funktioniert:

sagen, dass die sortierten Array enthält die folgenden Nummern: 1 2 3 4 5 6 7 8 9 9. Wie viele Nummern fehlen in diesem Array? Einziger. Uns fehlt die Nummer 0.

Wie viele Nummern sind an ihrem "richtigen" Ort? Nur die letzte 9. Dies ist der Grund, warum Ihr Code 9 anstelle von 1 zurückgibt.