Java Ponketmon: por qué la respuesta es min(tipos distintos, N/2)

Al seleccionar N/2 elementos de N para maximizar los tipos distintos, la respuesta es min(distinct types, N/2). No se pueden seleccionar más tipos que elementos ni inventar tipos ausentes de la entrada.

El ejercicio Ponketmon proporciona un N positivo par con N≤10 000 e identificadores de tipo de 1 a 200 000. Pide un recuento máximo, no una selección concreta.

Flujo de procesamiento

El número de tipos distintos y el límite de selección N/2 son cotas superiores. Su mínimo es alcanzable con las condiciones del ejercicio.

Contar tipos con HashSet

Guarda esta clase completa como Solution.java. El código del artículo original se compiló para Java 11 y se ejecutó en 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 conserva cada identificador una vez. Su tamaño es el número de tipos distintos u, mientras que k=nums.length / 2 es el número de plazas disponibles. Las frecuencias por tipo no son necesarias aquí.

Demostrar que el límite es alcanzable

Si u≥k, selecciona un elemento de cada uno de k tipos distintos. Si u<k, selecciona uno de cada tipo y completa las k-u plazas restantes con otros elementos. Solo se han usado u de los N elementos y k≤N, así que quedan suficientes. Por tanto, la cota superior min(u, k) es alcanzable.

Entrada	Tipos u	Plazas k	Respuesta
[3,1,2,3]	3	2	2
[3,3,3,2,2,2]	2	3	2
[7,7]	1	1	1

Con hashes adecuadamente dispersos, el tiempo esperado es O(N) y el espacio adicional O(u). Devolver los índices elegidos requeriría un procedimiento de construcción adicional; este método solo calcula el recuento solicitado.

Para entradas pequeñas, las comprobaciones comparan el resultado con la enumeración de todas las selecciones de N/2 posiciones. Las comprobaciones de longitud máxima cubren 10 000 tipos únicos y 10 000 copias de un mismo tipo. Validan los resultados sin medir la velocidad de la implementación hash.

Para un caso donde importa el número de duplicados, compara las frecuencias de nombres del corredor que no termina.