Fjern dubletter på stedet

Givet et sorteret array skal du beholde én kopi af hver værdi uden et ekstra array. Når du arbejder på stedet, sparer du hukommelse, og det er en klassisk opgave til jobsamtaler. 🧹

Når arrayet er sorteret, står hvert duplikat lige ved siden af sin kopi. Derfor sammenligner du kun naboer og aldrig hele arrayet.

Brug en slow-pointer, der markerer den senest gemte værdi, og en fast pointer, der gennemløber arrayet fremad og leder efter noget nyt.

Tænk på slow som skrivepositionen: Alt ved eller før den er allerede renset og entydigt.

Pointeren fast læser bare fremad. Den løber i forvejen og giver kun slow besked, når den finder en værdi, der endnu ikke er gemt.

Hvis a[fast] er lig med a[slow], er det en gentagelse, så du skal ikke gøre andet end at øge fast. Du springer stille og roligt duplikatet over.

Når a[fast] er forskellig, skal du flytte slow frem og kopiere den nye værdi dertil. På den måde overskriver du gamle duplikater med nye, entydige data.

Efter gennemløbet er slow + 1 antallet af entydige værdier, som alle ligger samlet forrest i arrayet.

Alt, der ligger efter det entydige præfiks, er overskydende data. Opgaven interesserer sig kun for de første slow + 1 elementer, så lad resten være.

Et tomt array har nul entydige værdier. Kontrollér n == 0, før du starter, så du ikke læser forbi slutningen.

Dette mønster med en langsom og en hurtig pointer bruger O(n) tid og O(1) ekstra plads, hvilket er præcis det, stramme hukommelsesbegrænsninger kræver.

I et sorteret array fjerner et par med en langsom og en hurtig pointer duplikater i ét O(n)-gennemløb uden ekstra plads og returnerer slow + 1 som antallet af entydige værdier. 🎉