En una palabra:
N es un número entero que representa una cantidad de contadores y el contador máximo permitido;A es una matriz que representa la operación realizada en un contador específico (por ejemplo, si A[0] es 1 y N es 3 , necesitamos agregar 1 a counter[0] );A es N+1 , todos los elementos del counter deben cambiarse al número más grande en la matriz del counter .Envié el código que escribí y obtuve solo un 60 % de rendimiento. ¿Porqué es eso? ¿De alguna manera debería abordar un problema la próxima vez para hacerlo más eficiente? ¿Cómo puedo mejorar?
function solution(N,A){ let counters = Array(N).fill(0); let maxCounter = 0; for(i=0;i<A.length;i++){ if(A[i]<=N){ counters[A[i]-1]++ if(counters[A[i]-1]>maxCounter){maxCounter = counters[A[i]-1]}; } else if(A[i]===N+1){ counters = Array(N).fill(maxCounter) } } return counters }Editar: no sabía que este sitio web no estaba destinado a preguntas sobre la mejora del código, gracias, preguntaré en otro lugar.
Una posible mejora sería, cuando necesite llenar toda la matriz con los nuevos contadores máximos, no cree una matriz completamente nueva para hacerlo; en su lugar, cambie la matriz existente.
else if(A[i]===N+1){ counters.fill(maxCounter) }Esto podría tener un gran efecto si hay muchos contadores.
Aquí hay una solución que usa un objeto que generará la matriz real solo una vez (después de aplicar todas las operaciones).
El objeto "rastreador" solo contendrá los índices y valores de aquellos contadores que tienen una operación. Digamos que N (es decir, el número "num" de contadores) es 50 000, pero solo 5000 contadores tienen una operación explícita en A (es decir, la matriz "arr"), solo esos 5000 elementos serán rastreados (usando el objeto "rastreador").
Fragmento de código
// alternative solution using object const counterOps = (num, arr) => { // the "tracker" object we will use to populate the result array const tracker = {}; // when "num+1" to reset all elements to "max", then // the "max" value is stored in "lastMaxSet" let lastMaxSet = 0; // helper method to get current max from "tracker" const getMax = obj => Math.max(...Object.values(obj)); // helper method to "set" "all" values to "max" const setMax = obj => { lastMaxSet = getMax(obj); Object.keys(obj).forEach(k => obj[k] = lastMaxSet); }; // iterate through "arr" and "apply" each "operation" arr.forEach(elt => { if (elt === num + 1) { // "reset to max" operation is applied setMax(tracker); } else { // a particular counter is incremented const k = elt - 1; tracker[k] ??= lastMaxSet; tracker[k]++; } }); // the "tracker" object is used to generate // the result-array on-the-fly return [...Array(num).fill(lastMaxSet)].map( (val, idx) => idx in tracker ? tracker[idx] : val ); }; console.log(counterOps(5, [3, 4, 4, 6, 1, 4, 4])); .as-console-wrapper { max-height: 100% !important; top: 0 }Pruebe y comparta sus comentarios si le ayudó en algo (con el rendimiento).
La puntuación del 60% en eficiencia se debe a los dos últimos casos de prueba en los que se realizan más de 10,000 operaciones de "contador máximo" . https://app.codility.com/demo/results/trainingA86B4F-NDB/
Cada una de esas operaciones tiene que iterar a través de la matriz de counter , que puede tener hasta 100,000 elementos. Eso da como resultado un total de 1 billion escrituras, por lo que el motivo del problema de rendimiento aparece rápidamente a la vista.
Para mejorar esto y reducir este número, podemos eliminar las operaciones consecutivas innecesarias de "contador máximo" , por ejemplo, introduciendo un indicador que indica si la matriz de counter ya está al máximo y no hay necesidad de iterar todo de nuevo.
Código de muestra:
const solution = (n, arr) => { const counter = new Array(n).fill(0); let max = 0, counterMaxed = false; for (let curr of arr) { if (curr > n) { if (!counterMaxed) { counter.fill(max); counterMaxed = true; } continue; } curr--; counter[curr]++; counterMaxed = false; if (counter[curr] > max) { max = counter[curr]; } } return counter; }; Esto obtiene una puntuación directa del 100% :
https://app.codility.com/demo/results/training3H48RM-6EG/