Cómo mejoro este algoritmo simple? - JavaScript

const arr = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 5, 8, 8];
const repeatedNums = arr.filter(function(item, pos, self) {
    return self.indexOf(item) < pos;
});
console.log(repeatedNums);

#5 Puedes hacer la operación del Set sin necesidad de iterar.

[...new Set(repeatedNums)].

De hecho si expresas o declaras repeatedNums como una función puedes reutilizarla para otros arrays.

const array = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 8, 5, 8, 8, 100, 130];
const repeatedNums = arr => arr.filter(function(item, pos, self) {
  return self.indexOf(item) < pos;
});

console.log(repeatedNums(array)) // Todos los duplicados
console.log([...new Set(repeatedNums(array))]); // Duplicados unicos

Otra forma por aquí...

const input = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 8, 5, 8, 8, 100, 130];
const repeatedNums = []; 
for (let i=input.length-1; i>0; --i) {
    const cur_num = input[i]; // Almacenamos el valor de la lista ya que lo vamos a usar varias veces...
    if (cur_num === input[i-1] && repeatedNums.indexOf(cur_num) === -1) { // Si el numero anterior es igual al numero actual es que está repetido y es consecutivo, lo añadimos a la lista de repetidos si no existe ya
        repeatedNums.push(cur_num); 
        --i; // Como sabemos que el número anterior es igual pues nos lo saltamos
    } 
} 

Si te dicen que quites el doble for será por que el algoritmo es muy ineficiente, tiene un coste exponencial. #4, #5 #6, #7 y #8 Tienen el mismo problema.

Para encontrar los duplicados con un coste lineal necesitas usar un Set, introducir los elementos y comprobar si ya existen.

const arr = [100, 100, 500, 500, 55555, 800, 5555, 130, 5, 5, 8, 8];
const findDuplicates = arr => {
    const set = new Set();
    const duplicates = [];
    arr.forEach(item => {
        if (set.has(item)) {
            duplicates.push(item);
        }
        set.add(item);
    });
    return duplicates;
}
console.log(findDuplicates(arr));

PD: El #9 es insuperable.

#12 ¿de donde sacas que "has" es más optimo que "indexOf"?

Con un test de 100.000.000 de registros en chromium:
Test_Array.indexOf(): 62.173095703125 ms
Test_Set.has(): 2131.112060546875 ms

#17
https://262.ecma-international.org/6.0/#sec-set.prototype.has
https://262.ecma-international.org/6.0/#sec-samevaluezero

#19 El test está incorrecto... le es más sencillo a "console.log" trabajar con booleanos que con Number.

Ese algoritmo es mejor al anterior, pero sigue siendo peor que usar un Set. Ordenar un array tiene un coste medio de nlogn, peor que linear.
Si en la prueba te sale mejor es por que el dato de entrada está ordenado con anterioridad al test. Si lo desordenas un poco para que el sort tenga que trabajar veras que es más lento.

#24 si pero no, depende de varios factores

• optimizas rendimiento, memoria o escalabilidad
• tus datos que estructura tienen, analisis de datos, tipos de datos

hay casos en que el set sera peor incluso para entradas muy grandes

que implementacion/algoritmo de set vas a usar? has resuelto solo para integers positivos? cualquier valor de int32 o int64? o tambien para []byte? has pensado en paralelizar y usar un filtro probabilistico para detectar colisiones? que hardware estas asumiendo que tiene tu maquina?

si se admite margen de error en la resupesta del 0.000...% dependiendo del tama;o de N, el OP te lo resuelvo con 1 for que ni termina. eso si es rapido. checkeas hasta que tu % de acierto es superior a tu budget de error. return.

de hecho segun el caso de uso de ese algoritmo, si es algo para repetidos sobre caches (sets) no hacen falta ningun for, segun la distribucion te puedo ir sacando randoms del array. y esto es muy habitual en caches distribuidas en el mundo real. yo he implementado algo parecido.

sobre el utlimo caso en la universidad se ense;a con el tema de NP, no podemos resolverlo en tiempo polinomial pero si comprovarlo, generas soluciones rapido y las compruevas en P. si tu algoritmo es "suficientemente bueno" aproximaras una solucion buena en tiempo P de un NP. de vuelta al OP, si comprovar que 1 elemento esta repetido o no es gratis, suele ser un filtro, (lo dificil es devolver TODOS los repetidos) es mejor devolver 1 random de la lista y comprovarlo, 2 operaciones, que no tratar de ejecutar 1 operacion buena. mejor 2 malas rapido que 1 buena lento. "eventual consistency" y esas cosas.

#26 no vas a encontrar un algoritmo mejor que el que ha planteado sarwaz de coste lineal. Una vez tengas el algoritmo si tienes 1000 procesadores, infinitos caches y suerte en la entrada de datos te dara la sensacion que tiene un coste menor, pero no es así.
Y todas tus propuestas no hacen más q complicar un problema muy sencillo de resolver.