Kaksoiskappaleiden poistaminen paikallaan
Käytä hidasta ja nopeaa osoitinta
Kaksoiskappaleiden poistaminen paikallaan on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Poista duplikaatit suoraan taulukosta
Kun annettuna on järjestetty taulukko, säilytä jokaisesta arvosta yksi kopio ilman ylimääräistä taulukkoa. Suoraan taulukossa toimiminen säästää muistia ja on klassinen haastattelutehtävä. 🧹
Miksi järjestys auttaa
Kun taulukko on järjestetty, jokainen duplikaatti on heti toisen samanlaisen alkion vieressä. Siksi sinun tarvitsee verrata vain naapureita, ei koko taulukkoa.
Kaksi roolia, kaksi osoitinta
Käytä slow-osoitinta merkitsemään viimeksi säilytettyä arvoa ja fast-osoitinta etsimään edempää jotain uutta.
slow = 0
fast = 1Slow-osoitin kirjoittaa
Ajattele slow-osoitinta kirjoituskohtana: kaikki sen kohdalla ja sitä ennen oleva on jo puhdistettu ja ainutkertaista.
Fast-osoitin lukee
Fast-osoitin vain lukee eteenpäin. Se kiitää edelle ja ilmoittaa slow-osoittimelle vain, kun löytää arvon, jota ei ole vielä säilytetty.
Ohita toistot
Jos a[fast] on yhtä suuri kuin a[slow], kyseessä on toisto, joten älä tee mitään muuta kuin kasvata fast-arvoa. Duplikaatti ohitetaan huomaamatta.
for fast in range(1, n):
if a[fast] == a[slow]:
continueLöytyi uusi arvo
Kun a[fast] eroaa arvosta a[slow], siirrä slow-osoitinta eteenpäin ja kopioi uusi arvo siihen. Näin vanhat duplikaatit korvautuvat uusilla, ainutkertaisilla arvoilla.
else:
slow += 1
a[slow] = a[fast]Vastaus on pituus
Läpikäynnin jälkeen slow + 1 on ainutkertaisten arvojen määrä, ja kaikki ne ovat taulukon alussa peräkkäin.
return slow + 1Jätä loppu huomiotta
Kaikki ainutkertaisen alkuosan jälkeen oleva on ylimääräistä jätettä. Tehtävässä tarvitaan vain slow + 1 ensimmäistä alkiota, joten jätä loppu ennalleen.
Muista tyhjä taulukko
Tyhjässä taulukossa ei ole ainutkertaisia arvoja. Tarkista ehto n == 0 ennen aloittamista, jotta et lue taulukon lopun yli.
if n == 0:
return 0Yksi läpikäynti, ei lisätilaa
Tämä slow-fast-kuvio toimii ajassa O(n) ja käyttää O(1) ylimääräistä tilaa, mikä on juuri sitä, mitä tiukat muistirajoitukset edellyttävät.
Pikatarkistus
Poistat duplikaatteja suoraan järjestetystä taulukosta slow- ja fast-osoittimilla.
Kertaus
Järjestetyssä taulukossa slow-fast-pari poistaa duplikaatit yhdellä O(n)-läpikäynnillä ilman ylimääräistä tilaa. Uniikkien arvojen määräksi palautetaan slow + 1. 🎉
Opi Python tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Kaksoiskappaleiden poistaminen paikallaan” ilmainen?
Kyllä – oppitunnin ”Kaksoiskappaleiden poistaminen paikallaan” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Competitive Programming Academy-kurssin, päivitä CoddyKit PROhon. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Kaksoiskappaleiden poistaminen paikallaan”?
Käytä hidasta ja nopeaa osoitinta Harjoittelet Competitive Programming Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Competitive Programming Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Competitive Programming Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.
Kuinka kauan ”Kaksoiskappaleiden poistaminen paikallaan”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Competitive Programming Academy-oppitunnilla?
Kyllä. Jokainen Competitive Programming Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Kaksi osoitinta järjestetyssä taulukossa
- Tietyn summan muodostavan parin etsiminen
- Kaksoiskappaleiden poistaminen paikallaan
- Kahden järjestetyn sekvenssin yhdistäminen