Rimuovere i duplicati sul posto

Dato un array ordinato, si conserva una sola copia di ogni valore senza usare un array aggiuntivo. Operare in place fa risparmiare memoria ed è una richiesta classica nei colloqui tecnici. 🧹

Quando l'array è ordinato, ogni duplicato si trova immediatamente accanto alla sua copia. È quindi sufficiente confrontare gli elementi vicini, senza esaminare l'intero array.

Si usa un puntatore slow che indica l'ultimo valore conservato e un puntatore fast che scorre in avanti alla ricerca di qualcosa di nuovo.

Si può considerare slow come la posizione di scrittura: tutto ciò che si trova in corrispondenza o prima di essa è già stato ripulito ed è unico.

Il puntatore fast si limita a leggere in avanti. Procede rapidamente e segnala slow solo quando individua un valore non ancora conservato.

Se a[fast] è uguale ad a[slow], si tratta di una ripetizione, quindi non si fa nulla e si avanza solo fast. Il duplicato viene semplicemente ignorato.

Quando a[fast] è diverso, si fa avanzare slow e si copia lì il nuovo valore. In questo modo i vecchi duplicati vengono sovrascritti con dati unici aggiornati.

Dopo la scansione, slow + 1 è il numero di valori unici, tutti raccolti nella parte iniziale dell'array.

Qualunque cosa si trovi dopo il prefisso di valori unici è solo materiale residuo. Il problema considera soltanto i primi slow + 1 elementi, quindi la coda può essere lasciata invariata.

Un array vuoto contiene zero valori unici. È necessario gestire il caso n == 0 prima di iniziare, per non leggere oltre la fine dell'array.

Questo schema slow-fast richiede tempo O(n) e spazio aggiuntivo O(1), esattamente ciò che serve quando i limiti di memoria sono rigidi.

Si stanno rimuovendo i duplicati in place da un array ordinato usando i puntatori slow e fast.

In un array ordinato, una coppia slow-fast rimuove i duplicati con un'unica scansione O(n) e senza spazio aggiuntivo, restituendo slow + 1 come numero di valori unici. 🎉