Quiero escribir una función que reciba dos secuencias: A y B y devuelva la secuencia C que debe contener todos los elementos de A (en orden) excepto aquellos que están presentes en B p veces.
Por ejemplo secuencias
A=[2,3,9,2,5,1,3,7,10]
B=[2,1,3,4,3,10,6,6,1,7,10,10,10]
Debería devolver C=[2,9,2,5,7,10]
Cuando p = 2
Lo escribí así:
function cSequence(a, b, p) { const times = {}; b.forEach((item) => { if (times[item]) { times[item] += 1; } else { times[item] = 1; } }); const pTimes = b.filter((item) => (times[item] == p ? true : false)); return a.filter((item) => !pTimes.includes(item)); }Pero, ¿hay una mejor manera de hacer esto en términos de complejidad de tiempo?
Además, ¿mi solución debería expresarse como O(3n) u O(n)?
¿Hay una mejor manera de hacer esto en términos de complejidad de tiempo?
¡No utilices includes() dentro de la devolución de llamada del filter ! Eso le da una complejidad de tiempo cuadrática. Ya tiene un mapa de búsqueda por elemento, ¡utilícelo directamente para lograr una solución lineal! Deshágase de los pTimes intermedios:
function cSequence(a, b, p) { const times = {}; for (const item of b) { if (item in times) { times[item] += 1; } else { times[item] = 1; } } return a.filter(item => times[item] != p); }¿Debe expresarse mi solución como
O(3n)uO(n)?
Es lo mismo. Los factores constantes se ignoran en la notación de Landau.
Puede usar Array.prototype.reduce() para crear un objeto bHash que contenga todas las ocurrencias del número total
Y luego, Array.prototype.filter() matriz A excluyendo aquellos elementos que se repiten en la matriz B p veces
Código:
const A = [2,3,9,2,5,1,3,7,10] const B = [2,1,3,4,3,10,6,6,1,7,10,10,10] const p = 2 const cSequence = (arrA, arrB, p) => { const bHash = arrB.reduce((a, c) => (a[c] ??= 0, a[c]++, a), {}) return arrA.filter(n => bHash[n] !== p) } console.log(cSequence(A, B, p))