Tenía 2 matrices (txs e intervalo) y quiero que el intervalo incluya txs que tenían una fecha entre desde y hasta (incluir).
const txs = [ { price: 1, date: 1 }, { price: 3, date: 2 }, { price: 1.7, date: 4 } ]; const interval = [ { from: 1, to: 2, txs: [] }, { from: 2, to: 3, txs: [] }, { from: 3, to: 4, txs: [] } ];Resultado Esperado
[ { from: 1, to: 2, txs: [{ price: 1 }, { price: 3 }] }, { from: 2, to: 3, txs: [{ price: 3 }] }, { from: 3, to: 4, txs: [{ price: 1.7 }] } ]Y esta es mi solución en O(n^2)
for (let i of interval) { for (let j of txs) { if (j.date >= i.from && j.date <= i.to) { i.txs.push({ price: j.price }); } } }esto es solo un ejemplo. el txs real y el intervalo pueden tener más de 10.000 elementos. ¿Hay alguna solución que se pueda hacer en O(n) u O(n log n)?
Permítanme llamar a la longitud de txs n ya la de intervals m . Siguiendo la pista de cucaracho , tienes un precálculo O( n log( n )). Encontrar el primer "txs" para incluir (si corresponde) toma O (log n ) para cada intervalo. Agregar un txs debe tomar O(1) para un total de O( n log( n ) + m log( n ) + mn ) = O(( n + m ) log( n ) + mn ).
Para eliminar ese molesto término mn ("tamaño de salida"), busque los primeros txs que no se incluirán y para cada intervalo represente los txss que se incluirán especificando este además del primero.
Para intervalos que no se superponen, simplemente ordenar ambos arreglos y caminar ambos puede ser más rápido, una influencia es el tamaño relativo del arreglo.