0
237
ViewsCuente el total de la matriz de números ignorando el número de superposición
Tengo este tipo de problema y trato de resolverlo usando Javascript/Go. Dada esta matriz de conjuntos de números, me gustaría encontrar la suma de los números. El cálculo debe ignorar la superposición y considerar contarla como una sola vez.
const nums = [[10, 26], [43, 60], [24,31], [40,50], [13, 19]]Sería algo así como seguir si se traduce a la imagen.
El resultado debería 41
las reglas son
- El conjunto superpuesto de números (área rosa) debe contarse una vez.
- Cuente la suma total del área verde.
- Total para ambos.
Cualquier ayuda será apreciada.
3 answers
Answer question0
Aquí hay una solución de una sola línea usando javascript (suponiendo que la respuesta correcta sea 41 en lugar de 42 ).
La idea es iterar todos los números de intervalo y ponerlos en una sola matriz, luego recortar todos los duplicados usando Set . La complejidad del tiempo no es óptima, pero es lo suficientemente corta.
const nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]]; const total = new Set(nums.reduce((acc, [from, to]) => [...acc, ...Array.from({ length: to - from }, (_, i) => i + from)], [])).size; console.log(total);No estoy seguro de cómo hacerlo con go , pero es solo una propuesta.
0
Aquí está mi versión:
const getCoverage = arr => arr .reduce((results, el) => { if (!results.length) { return [el]; } let running = true, i = 0; while(running && i < results.length) { if (el.some(n => n >= results[i][0] && n <= results[i][1])) { results[i] = [ Math.min(el[0], results[i][0]), Math.max(el[1], results[i][1]) ]; running = false; } i++; } if (running) { results.push(el); } return results; }, []) .reduce((total, el) => el[1] - el[0] + total, 0); console.log( getCoverage([[10, 26], [43, 60], [24,31], [40,50], [13, 19]]) );El primer reductor fusiona intervalos superpuestos (y adyacentes) y el segundo suma las diferencias de los fusionados resultantes.
0
Puede ordenar los pares y reducir al verificar el segundo valor y luego agregar los deltas para obtener la suma.
const nums = [[10, 26], [43, 60], [24, 31], [40, 50], [13, 19]], result = nums .sort((a, b) => a[0] - b[0] || a[1] - b[1]) .reduce((r, [...a]) => { const last = r[r.length - 1]; if (last && last[1] >= a[0]) last[1] = Math.max(last[1], a[1]); else r.push(a); return r; }, []) .reduce((s, [l, r]) => s + r - l, 0); console.log(result)