Estoy trabajando en un desafío de LeetCode 26. Eliminar duplicados de la matriz ordenada :
Dada una matriz de números
numsordenados en orden no decreciente , elimine los duplicados en el lugar de modo que cada elemento único aparezca solo una vez . El orden relativo de los elementos debe mantenerse igual .Dado que es imposible cambiar la longitud de la matriz en algunos idiomas, debe colocar el resultado en la primera parte de la matriz
nums. Más formalmente, si haykelementos después de eliminar los duplicados, entonces los primeroskelementos denumsdeberían contener el resultado final. No importa lo que dejes más allá de los primeroskelementos.Devuelve
kdespués de colocar el resultado final en las primeraskranuras denums.No asigne espacio extra para otra matriz. Debe hacer esto modificando la matriz de entrada en el lugar con memoria adicional O (1).
No estoy seguro de por qué no se acepta mi respuesta. Creo que estoy malinterpretando algo simple.
Mi solución solo devuelve una matriz vacía aunque parece que tengo la respuesta correcta para la prueba de referencia. ¿Hay algo que estoy pasando por alto en la implementación con respecto a las reglas del desafío? splice edita elementos en su lugar... así que pensé que estaría bien.
Cualquier sugerencia sera apreciada.
var removeDuplicates = function(nums) { const map = new Map(); let count = 0; nums.forEach((item, i) => { if (map.get(item) === undefined){ map.set(item, i); } else if (map.get(item) !== undefined) { nums.splice(i, 1); nums.push('_'); count ++; } }); return count; };También publiqué esto como una pregunta en la sección de discusión de LeetCode .
No debe separar los elementos de una matriz que está iterando, ya que dicha iteración se basa en un índice creciente y la eliminación hará que los valores de la matriz se desplacen hacia la izquierda. Entonces este doble efecto hará que saltes los valores de la matriz.
Además, debe evitar empalmar todos juntos, ya que representa una complejidad de tiempo O(n).
Además, la asignación dice "No asigne espacio adicional... Debe hacer esto... con O(1) memoria adicional". , por lo que recopilar valores en un Map no es lo que se supone que debe hacer. Como la matriz de entrada está ordenada, tampoco necesita este mapa.
En su lugar, use dos índices: uno que se usará para leer un valor y otro donde se escribirá un valor. El primero se adelantará al segundo cuando haya duplicados.
var removeDuplicates = function(nums) { if (nums.length == 0) return 0; let k = 0; for (let value of nums) { if (value != nums[k]) { nums[++k] = value; } } return k + 1; }; Tenga en cuenta que no es necesario modificar la length de la matriz, como dice el desafío del código:
...los primeros
kelementos denumsdeberían contener el resultado final. No importa lo que dejes más allá de los primeroskelementos.
Al eliminar el elemento con el índice i usando splice , los elementos de la matriz se desplazan. Comienza la siguiente iteración, observa el elemento en el índice i + 1 . Pero a medida que los elementos cambiaron, se pierde el elemento que estaba en la posición i + 1 y se convirtió en el elemento en la posición i después del cambio.
Asumo que sería incorrecto de mi parte publicar una respuesta correcta ya que es un desafío, otros participantes deberían resolverlo por sí mismos y no copiar y pegar una respuesta desde aquí. Así que solo estoy mostrando lo que obtenemos usando la solución actual:
const removeDuplicates = function(nums) { const map = new Map(); let count = 0; nums.forEach((item, i) => { if (map.get(item) === undefined){ map.set(item, i); } else if (map.get(item) !== undefined) { nums.splice(i, 1); nums.push('_'); count++; } }); return count; }; const nums = [0,0,1,1,1,2,2,3,3,4]; // Input array const expectedNums = [0,1,2,3,4]; // The expected answer with correct length const k = removeDuplicates(nums); // Calls your implementation console.log(nums.join(',')) console.log(expectedNums.join(','))