Fehlenden Läufer in Java über Namenshäufigkeiten finden

Um den fehlenden Läufer zu finden, zählen Sie Personen je Name, statt nur die Existenz eines Namens zu prüfen. Ziehen Sie die Finisherhäufigkeiten von den Teilnehmerhäufigkeiten ab. Die Aufgabe garantiert, dass genau ein Name mit Anzahl 1 verbleibt.

Die Eingabebedingungen erlauben bis zu 100.000 Teilnehmer, einen Finisher weniger und gleiche Namen. Namen bestehen aus 1–20 englischen Kleinbuchstaben. Die Finisherliste wird als gültige Teilnehmerliste mit einer entfernten Person vorausgesetzt.

Ablauf

Alle Teilnehmer zählen, jeden Finisher abziehen und den Namen mit einer verbleibenden Person zurückgeben.

Die Anzahldifferenz speichern

Speichern Sie die vollständige Klasse als Solution.java. Der Code des Ausgangsartikels wurde für Java 11 kompiliert und auf JDK 17 ausgeführt.

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> counts = new HashMap<>();
        for (String name : participant) counts.merge(name, 1, Integer::sum);
        for (String name : completion) counts.put(name, counts.get(name) - 1);
        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) return entry.getKey();
        }
        throw new IllegalArgumentException("Expected exactly one missing runner");
    }
}

merge(name, 1, Integer::sum) beginnt einen neuen Namen bei 1 und erhöht vorhandene Anzahlen. Jeder Finisher verringert die Anzahl dieses Namens um eins. Bei Teilnehmern [ana, bob, ana] und Finishern [bob, ana] verbleibt für ana 2 - 1 = 1.

Eine Set-Differenz würde verlieren, dass zwei Personen ana hießen. Anzahlen erhalten die Mehrfachvorkommen und bilden so eine fehlende Person ab. Eine andere Reihenfolge des Finisherarrays ändert das Ergebnis nicht.

Nicht auf die HashMap-Reihenfolge vertrauen

HashMap garantiert keine Iterationsreihenfolge. Den ersten positiven Eintrag zurückzugeben funktioniert, weil gültige Eingaben genau einen solchen Eintrag übrig lassen, nicht wegen einer bestimmten Reihenfolge. Der Code gibt den Namen mit verbleibender Anzahl 1 zurück.

Die abschließende Ausnahme ist keine vollständige Eingabevalidierung. Eine allgemeine Abgleich-API bräuchte weitere Regeln und Prüfungen für unbekannte Finisher oder mehrere fehlende Personen.

Bei auf 20 begrenzter Namenslänge und durchschnittlich konstanten Hashoperationen beträgt die Laufzeit O(n), mit O(u) zusätzlichem Speicher für u verschiedene Namen. Kein Benchmark belegt, dass Streams oder Schleifen allgemein schneller sind.

Wenn nur verschiedene Arten zählen, reicht ein Set. Vergleichen Sie die Auswahlgrenze der Ponketmon-Aufgabe.