Estoy trabajando en el desafío Code Wars Número faltante en la progresión aritmética desordenada :
Si nunca ha escuchado el término Progresión aritmética, consulte un desafío de código anterior :
Una progresión aritmética se define como aquella en la que existe una diferencia constante entre los términos consecutivos de una serie dada de números. [...] Sin embargo, hay un problema: falta exactamente un término de la serie original en el conjunto de números que se le ha dado. El resto de la serie dada es el mismo que el AP original. Encuentra el término que falta.
Y aquí hay una versión desordenada. Intente si puede sobrevivir a listas de números MASIVOS (lo que significa que se debe considerar el límite de tiempo). :D
Nota: No tenga miedo de que falte el elemento mínimo o máximo en la lista, por ejemplo, [4, 6, 3, 5, 2] falta 1 o 7, pero este caso está excluido del kata (es decir, el código desafío).
Ejemplo:
find([3, 9, 1, 11, 13, 5]) # => 7
El código de mi solución funciona bien en el 99 % de los casos de prueba. Sin embargo, una prueba aleatoria con una entrada lo suficientemente grande siempre excede el tiempo de ejecución permitido.
function find(seq) { function compareNumbers(a, b) { return a - b; } let arr = [...seq].sort(compareNumbers); let difference = arr[1]-arr[0]; let arrLen = arr.length; let i=0; while(i<arrLen){ if(arr[i+1]-arr[i]!==difference) return arr[i] + difference; i++; } }Supongo que hay que hacer algunas mejoras en el algoritmo de clasificación o en el bucle while. Intenté reemplazar el algoritmo de clasificación con uno QuickSort, pero eso no ayudó.
Como el desafío del código garantiza que el mínimo y el máximo estén presentes en la entrada, puede derivar el paso de la siguiente información:
Dado el mínimo y el paso, puede recorrer fácilmente la secuencia de valores esperados y verificar que estén en el conjunto de valores de entrada.
Aquí hay una implementación:
function find(seq) { let low = seq[0]; let high = low; for (let i of seq) { if (i < low) low = i; else if (i > high) high = i; } let step = (high - low) / seq.length; let set = new Set(seq); for (let i = low + step; i < high; i += step) { if (!set.has(i)) return i; } } NB: No Math.min(...seq) aquí, en cuanto a matrices muy grandes que tendrán limitaciones de tamaño de pila.