Problema
Los árboles de decisión dividen los datos en grupos lo más puros posible. La impureza de Gini mide cuán mezcladas están las etiquetas de un grupo:
Gini = 1 - Σ pₖ²
donde pₖ es la proporción de etiquetas de la clase k. Un grupo con una sola clase tiene impureza 0; una mezcla igual de dos clases tiene impureza 0.5.
Implementa gini_impurity(labels).
Entrada
labels: Las etiquetas de clase del grupo.
Salida
Devuelve la impureza de Gini como número decimal.
Restricciones
1 ≤ longitud ≤ 10 000
Cada etiqueta tiene de 1 a 20 caracteres
Ejemplos
Entrada:
labels = ["yes", "yes", "no", "no"]
Salida esperada:
expected = 0.5
Entrada:
std::vector<std::string> labels = {"yes", "yes", "no", "no"};
Salida esperada:
double expected = 0.5;
Entrada:
string[] labels = new string[] {"yes", "yes", "no", "no"};
Salida esperada:
double expected = 0.5;
Explicación
La mitad son yes y la mitad no: 1 - (0.5² + 0.5²) = 1 - 0.5 = 0.5, la mayor mezcla posible en un grupo de dos clases.
Entrada:
labels = ["cat", "cat", "cat"]
Salida esperada:
expected = 0.0
Entrada:
std::vector<std::string> labels = {"cat", "cat", "cat"};
Salida esperada:
double expected = 0.0;
Entrada:
string[] labels = new string[] {"cat", "cat", "cat"};
Salida esperada:
double expected = 0.0;
Explicación
Una sola clase: 1 - 1² = 0. El grupo es puro.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Cuenta cuántas veces aparece cada label, porque la impureza solo depende de la distribución de labels.
Pista 2
Convierte los conteos en fracciones del grupo total y luego mide qué tan lejos está el grupo de ser puro.
Pista 3
Un grupo con un solo label debe dar cero, mientras que una mezcla equilibrada dará un valor mayor.
Complejidad esperada
tiempo O(n), espacio extra O(k)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.