Valmistautuminen ohjelmointihaastatteluihin · Oppitunti

Inversiot BIT:n avulla

Laske väärässä järjestyksessä olevat parit tehokkaasti

Oppitunti 2/413 vaihetta

Inversiot BIT:n avulla on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/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 Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Mikä inversio on

Inversio on pari i < j, jossa a[i] > a[j]. Se on yksi järjestyksestä poikkeava pari, ja niiden määrä kertoo, kuinka epäjärjestyksessä taulukko on.

Miksi inversiot ovat tärkeitä

Inversioiden määrä vastaa niiden vaihtojen määrää, jotka kuplalajittelu tekisi. Kilpailutehtävät piilottavat tämän usein järjestys- ja epäjärjestyskysymyksiin.

Naivi laskenta on liian hidasta

Kaikkien parien tarkistaminen vie ajan O(n^2). Kun n on noin 100 000, tarkistuksia tulee kymmenen miljardia, mikä ylittää aikarajan moninkertaisesti. Tarvitsemme tehokkaamman menetelmän. 🐢

BIT-rakenteen idea

Käykää taulukko läpi vasemmalta oikealle ja kysykää: kuinka monta aiempaa alkiota on nykyistä suurempia? Fenwick-puu vastaa tähän kysymykseen käsittelyn aikana.

Laskekaa esiintymistiheyksien avulla

BIT tallentaa arvojen esiintymistiheystaulukon. update(v, 1) kirjaa, että arvo v on esiintynyt tähän mennessä käsittelyssä.

update(v, 1)

Suuremmat arvot muodostavat loppuosan

Arvoa v suuremmat aiemmat arvot saadaan vähentämällä v:hen asti nähtyjen arvojen määrä kaikista nähdyistä arvoista. i:nnen alkion kohdalla tämä on i − query(v).

inv += i - query(v)

Koordinaattien pakkaaminen

Jos arvot ovat suuria tai negatiivisia, muuntakaa ne ensin järjestysluvuiksi 1..n. Tämä pakkaaminen pitää BIT-rakenteen pienenä muuttamatta arvojen järjestystä.

rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}

Koko läpikäynti

Käykää taulukko silmukassa läpi, lisätkää jokaisen alkion suurempien arvojen määrä kokonaismäärään ja lisätkää sitten nykyinen arvo rakenteeseen. Kertyvä kokonaissumma on inversioiden määrä.

for i, v in enumerate(a):
    inv += i - query(rank[v])
    update(rank[v], 1)

Aikavaativuus on n log n

Jokainen alkio aiheuttaa yhden kyselyn ja yhden päivityksen, jotka molemmat toimivat ajassa O(log n). Koko laskenta valmistuu ajassa O(n log n). 🚀

Yhdistämislajittelu on sukulaismenetelmä

Yhdistämislajittelu laskee inversiot myös ajassa O(n log n) yhdistämisvaiheen aikana. BIT-versio on usein lyhyempi kirjoittaa kiireessä.

Varokaa laskurin ylivuotoa

Inversioiden määrä voi olla noin n:n neliö jaettuna kahdella, mikä on valtava luku. Pythonin kokonaisluvut ovat rajoittamattomia, mutta muissa kielissä tarvitsette 64-bittisen tyypin.

Pikatarkistus

Testatkaa, hallitsetteko läpikäynnin aikavaativuuden.

Vastaa interaktiivisessa oppitunnissa

Kertaus: epäjärjestyksen laskeminen

Laskitte inversiot ajassa O(n log n) käymällä taulukon läpi vasemmalta oikealle ja kysymällä BIT-rakenteelta, kuinka monta suurempaa arvoa oli tullut aiemmin. Pakatkaa arvot tarvittaessa. ✅

Aloita maksutta

Opi Valmistautuminen ohjelmointihaastatteluihin 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: 90
Oppitunnit: 360

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Inversiot BIT:n avulla” ilmainen?

Kyllä – oppitunnin ”Inversiot BIT:n avulla” 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 Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Inversiot BIT:n avulla”?

Laske väärässä järjestyksessä olevat parit tehokkaasti Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.

Kuinka kauan ”Inversiot BIT:n avulla”-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ä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?

Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-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

← Takaisin: Valmistautuminen ohjelmointihaastatteluihin