Solución de prueba de demostración de Codility

Recientemente me encontré con una tarea de demostración de Codility . Lo encontré lo suficientemente interesante como para publicarlo aquí.

Al principio, quería usar un algoritmo codicioso , rastreando el número entero positivo mínimo hasta el momento . Tome la siguiente matriz: [1, 3, 6, 4, 1, 2]. Vamos a iterarlo. El primer número es 1. Entonces, el entero mínimo que no está en esta matriz hasta ahora es 2. Luego está 3. Entonces, el entero mínimo que no está en esta matriz hasta ahora sigue siendo 2. Todo va bien hasta que finalmente encuentro 2 en el final de esta matriz. Entonces, ¿cómo se supone que debo encontrar una respuesta, 5, con este enfoque? Bueno, me temo que simplemente no funciona aquí. Entonces se hizo obvio que necesito recordar de alguna manera todos los números encontrados.

¿Cuál es la mejor manera de detectarlos? El enfoque que primero viene a la mente es tener una matriz de patrones, una especie de tamiz, el que contiene todos los números enteros positivos dentro de un intervalo dado. Y sería muy útil si sus claves coincidieran con los valores. Entonces, con cada número entero que encuentro en la matriz de entrada, encuentro una clave correspondiente en una matriz de patrones y marco su valor como, digamos, nulo:

$patrón = rango (0, 100000);

foreach ($a como $valor) {$patrón[$valor] = nulo ;}

Después de eso, todo lo que necesito es iterarlo y encontrar la primera clave con un valor no nulo. Pero antes de eso, quiero asegurarme de que no obtendré 0 como respuesta, ya que no es un número entero positivo. Así que eliminé el primer elemento en mi matriz de patrones. Y hay un caso límite. ¿Qué sucede si obtengo todos los números enteros dentro de un intervalo determinado, [1, 100000]? La respuesta debería ser 100001. Así que creo una matriz de patrones con el supremo igual a 100001:

solución de función ( matriz $a) {$patrón = rango (0, 100001);

 **foreach** ($a **as** $value) { $pattern\[$value\] = **null**; } **unset**($pattern\[0\]); **for** ($i = 1; $i <= _count_($pattern); $i++) { **if** (!_is\_null_($pattern\[$i\])) { **return** $i; } }

}

¡Voila!