La pregunta era implementar una función llamada countUniqueValues , que acepta una matriz ordenada y cuenta los valores únicos en la matriz. Puede haber números negativos en la matriz, pero siempre estará ordenada.
Usé el patrón de punteros múltiples para resolver esta pregunta de modo que tenga una complejidad de tiempo de O(n) y una complejidad de espacio de O(1). Usé dos enfoques diferentes, uno con un ciclo for y otro con un ciclo while .
¿Cuál de estos enfoques es mejor?
function countUniqueValues(arr) { if (arr.length === 0) return 0; let pointer1 = 0; for (let pointer2 = 1; pointer2 < arr.length; pointer2++) { if (arr[pointer1] !== arr[pointer2]) { pointer1++; arr[pointer1] = arr[pointer2]; } } return pointer1 + 1; } function countUniqueValues(arr) { if (arr.length === 0) return 0; let pointer1 = 0; let pointer2 = pointer1 + 1; while (pointer2 < arr.length) { if (arr[pointer1] !== arr[pointer2]) { pointer1++; arr[pointer1] = arr[pointer2]; pointer2++; } else if (arr[pointer1] === arr[pointer2]) { pointer2++; } } return arr.slice(0, pointer1 + 1).length; } Complejidad de tiempo esperada: O(n)
Complejidad espacial esperada: O(1)
Usar for en lugar de while loop con exactamente la misma idea no es un enfoque diferente.
La lógica es correcta, pero podría haber sido mucho más simple. Desea encontrar esas posiciones en matrices donde los elementos son diferentes (bordes). Ahora su respuesta final es <#border>+1 .
let border = 0; for (let i = 1; i < arr.length; i++) { if (arr[i - 1] != arr[i]) { border++; } } return border+1;No necesita cambiar la matriz, no necesita mantener dos punteros.