Java Ponketmon: Warum min(verschiedene Typen, N/2) die Antwort ist

Werden N/2 Elemente aus N gewählt, um die Zahl verschiedener Typen zu maximieren, lautet die Antwort min(distinct types, N/2). Es lassen sich weder mehr Typen als Elemente wählen noch Typen erfinden, die nicht in der Eingabe vorkommen.

Die Ponketmon-Aufgabe liefert ein positives gerades N≤10.000 und Typ-IDs von 1 bis 200.000. Gefragt ist eine maximale Anzahl, keine bestimmte Auswahl.

Ablauf

Die Typanzahl und die Auswahlgrenze N/2 sind beide Obergrenzen. Unter den Aufgabenbedingungen ist ihr Minimum erreichbar.

Typen mit HashSet zählen

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.HashSet;
import java.util.Set;

public class Solution {
    public int solution(int[] nums) {
        Set<Integer> kinds = new HashSet<>();
        for (int kind : nums) kinds.add(kind);
        return Math.min(kinds.size(), nums.length / 2);
    }
}

HashSet behält jede ID einmal. Seine Größe ist die Anzahl verschiedener Typen u, während k=nums.length / 2 die verfügbaren Auswahlplätze zählt. Häufigkeiten je Typ sind hier unnötig.

Zeigen, dass die Grenze erreichbar ist

Für u≥k wählen Sie je ein Element aus k verschiedenen Typen. Für u<k wählen Sie zuerst ein Element jedes Typs und füllen die übrigen k-u Plätze mit anderen Elementen. Von N Elementen wurden erst u benutzt; wegen k≤N bleiben genug übrig. Somit ist die Obergrenze min(u, k) erreichbar.

Eingabe	Typen u	Plätze k	Antwort
[3,1,2,3]	3	2	2
[3,3,3,2,2,2]	2	3	2
[7,7]	1	1	1

Bei angemessen verteilten Hashwerten beträgt die erwartete Laufzeit O(N) und der zusätzliche Speicherbedarf O(u). Die Rückgabe gewählter Indizes würde ein weiteres Konstruktionsverfahren erfordern. Diese Methode berechnet nur die von der Aufgabe verlangte Anzahl.

Für kleine Eingaben vergleichen die Prüfungen mit der Aufzählung jeder Auswahl von N/2 Positionen. Prüfungen der maximalen Länge umfassen 10.000 unterschiedliche Typen und 10.000 Exemplare eines Typs. Sie prüfen Ergebnisse, ohne die Geschwindigkeit der Hashimplementierung zu messen.

Für einen Fall, in dem die Anzahl der Duplikate wichtig ist, vergleichen Sie Namenshäufigkeiten beim fehlenden Läufer.