Wie kann ich doppelte Ganzzahlen in einem Java-Array effizient erkennen?

Duplikate in einem Java-Array erkennen: Eine Reise

Im Java-Bereich ist eine häufig anzutreffende integrale Aufgabe die Suche nach doppelten Elementen innerhalb eines Arrays von Ganzzahlen (int []). Beim Versuch, diese Duplikate zu identifizieren, stößt man jedoch häufig auf eine Falle. Lassen Sie uns das Problem und seine Lösungen untersuchen.

Bedenken Sie den folgenden Code:

int[] zipcodelist = // ...

duplicates = false;
for(j = 0; j < zipcodeList.length; j++){
    for(k = 0; k < zipcodeList.length; k++){
        if (zipcodeList[k] == zipcodeList[j]){
            duplicates = true;
        }
    }
}

Dieser Code soll feststellen, ob die angegebene Postleitzahlenliste doppelte Elemente enthält. Allerdings werden Szenarios, in denen keine Duplikate vorhanden sind, nicht berücksichtigt. Infolgedessen erweisen sich Duplikate immer als wahr.

Identifizierung des Fehlers

Um den Fehler zu verstehen, analysieren wir die Logik. Der Code verfügt über verschachtelte Schleifen, die jedes Element in der Liste mit jedem anderen Element vergleichen. Wenn zwei beliebige Elemente übereinstimmen, wird „Duplikate“ auf „True“ gesetzt, was das Vorhandensein von Duplikaten anzeigt. Wenn jedoch keine Duplikate vorhanden sind, vergleicht die Schleife zwangsläufig ein Element mit sich selbst. Für jedes Element würde dieser Selbstvergleich Duplikate auf „true“ setzen.

Ein korrigierter Ansatz

Um die korrekte Erkennung von Duplikaten sicherzustellen, sollte der Code Selbstvergleiche ausschließen. Eine Möglichkeit, dies zu erreichen, besteht darin, die Struktur der verschachtelten Schleife wie folgt zu ändern:

duplicates=false;
for (j=0;j<zipcodeList.length;j++)
  for (k=j+1;k<zipcodeList.length;k++)
    if (k!=j &amp;&amp; zipcodeList[k] == zipcodeList[j])
      duplicates=true;

Diese Modifikation überspringt Selbstvergleiche, indem die innere Schleife beim nächsten Index (k=j 1) beginnt.

Erforschung alternativer Lösungen

Während der korrigierte Ansatz effektiv funktioniert, stehen schnellere Alternativen zur Verfügung. Betrachten Sie die folgende Hashmap-basierte Lösung:

boolean duplicates(final int[] zipcodelist)
{
  Set<Integer> lump = new HashSet<Integer>();
  for (int i : zipcodelist)
  {
    if (lump.contains(i)) return true;
    lump.add(i);
  }
  return false;
}

Diese Lösung verwendet einen Hash-Satz, um effizient nach doppelten Elementen zu suchen. Jedes Element wird dem Hash-Set hinzugefügt, und wenn ein Element bereits vorhanden ist, bedeutet es ein Duplikat.

Ein weiterer effizienter Ansatz ist die Verwendung einer Bitmap:

static boolean duplicates(final int[] zipcodelist)
{
   final int MAXZIP = 99999;
   boolean[] bitmap = new boolean[MAXZIP+1];
   java.util.Arrays.fill(bitmap, false);
   for (int item : zipcodelist)
     if (!(bitmap[item] ^= true)) return true;
   }
   return false;
}

Diese Lösung erstellt eine Bitmap Array mit einer Größe, die dem maximal möglichen Wert im Array entspricht (MAXZIP). Anschließend wird die Bitmanipulation verwendet, um das entsprechende Bit für jedes im Eingabearray gefundene Element zu setzen. Wenn ein Bit bereits gesetzt ist, deutet dies auf ein Duplikat hin.

Benchmarking-Ergebnisse

Um die Leistung dieser Ansätze zu bewerten, haben wir einen Benchmark mit unterschiedlichen Listengrößen durchgeführt. Die Ergebnisse zeigten, dass sich der Bitmap-Ansatz als klarer Effizienzsieger herausstellte, insbesondere bei größeren Listen:

Array Size	Bitmap (ms)	Hash Set (ms)	Nested Loops (ms)
10	0.0	0.0	0.0
1,000	0.0	0.0	0.0
10,000	0.0	0.0	100.0
100,000	0.0	0.16	9,923.3

Fazit

Das Identifizieren von Duplikaten in einem Java-Array kann eine unkomplizierte Aufgabe sein, sobald die Fallstricke verstanden sind. Durch die Vermeidung von Selbstvergleichen oder die Nutzung alternativer Ansätze wie Hash-Sets und Bitmaps kann eine effiziente und genaue Duplikaterkennung erreicht und die Leistung Ihrer Java-Anwendungen optimiert werden.

Das obige ist der detaillierte Inhalt vonWie kann ich doppelte Ganzzahlen in einem Java-Array effizient erkennen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!