Java Ponketmon : pourquoi la réponse est min(types distincts, N/2)

Pour sélectionner N/2 éléments parmi N en maximisant les types distincts, la réponse est min(distinct types, N/2). On ne peut sélectionner plus de types que d’éléments ni inventer des types absents de l’entrée.

L’exercice Ponketmon fournit un N positif pair avec N≤10 000 et des identifiants de type de 1 à 200 000. Il demande un nombre maximal, pas une sélection particulière.

Déroulement

Le nombre de types distincts et la limite de sélection N/2 sont deux bornes supérieures. Leur minimum est atteignable dans les conditions de l’exercice.

Compter les types avec HashSet

Enregistrez cette classe complète dans Solution.java. Le code de l’article source a été compilé pour Java 11 et exécuté sur JDK 17.

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 conserve chaque identifiant une fois. Sa taille est le nombre de types distincts u, tandis que k=nums.length / 2 est le nombre de places disponibles. Les fréquences par type sont inutiles ici.

Montrer que la borne est atteignable

Si u≥k, choisissez un élément de chacun de k types différents. Si u<k, choisissez un élément de chaque type, puis complétez les k-u places restantes avec d’autres éléments. Seuls u des N éléments ont été utilisés et k≤N : il en reste donc assez. Ainsi, la borne supérieure min(u, k) est atteignable.

Entrée	Types u	Places k	Réponse
[3,1,2,3]	3	2	2
[3,3,3,2,2,2]	2	3	2
[7,7]	1	1	1

Avec des valeurs de hachage correctement dispersées, le temps attendu est O(N) et l’espace supplémentaire O(u). Renvoyer les indices sélectionnés nécessiterait une procédure de construction supplémentaire ; cette méthode calcule uniquement le nombre demandé.

Pour les petites entrées, les vérifications comparent le résultat à l’énumération de toutes les sélections de N/2 positions. Les vérifications de longueur maximale couvrent 10 000 types uniques et 10 000 exemplaires d’un seul type. Elles valident les résultats sans mesurer la vitesse de l’implémentation du hachage.

Pour un cas où le nombre de doublons importe, comparez les fréquences des noms du coureur manquant.