bisect_left ja bisect_right
Etsi lisäyskohdat järjestetystä listasta
bisect_left ja bisect_right 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.
Hae ilman perusrunkoa
Pythonin bisect-moduuli tarjoaa testatun binäärihaun järjestetyille listoille. Kun et kirjoita silmukkaa itse, sinun ei tarvitse korjata yhden poikkeaman virheitä.
import bisectLisäyskohdat, ei totuusarvoja
True- tai false-arvon sijaan bisect palauttaa indeksin, johon arvo lisättäisiin listan järjestyksen säilyttämiseksi. Juuri tämä indeksi on toiminnon todellinen voima.
a = [1, 3, 3, 3, 7]bisect_left kallistuu vasemmalle
bisect_left palauttaa ensimmäisen kohdan, johon arvo voisi tulla. Duplikaattien tapauksessa se sijoittuu kaikkien samanarvoisten alkioiden eteen, ei koskaan niiden jälkeen.
bisect.bisect_left(a, 3) # 1bisect_right kallistuu oikealle
bisect_right palauttaa kohdan heti viimeisen samanarvoisen alkion jälkeen. Duplikaattien tapauksessa se sijoittuu kaikkien vastaavien arvojen perään.
bisect.bisect_right(a, 3) # 4Laske samanarvoiset alkiot
Vähennä nämä kaksi arvoa toisistaan duplikaattien laskemiseksi luokassa O(log n). right miinus left antaa täsmälleen arvon esiintymiskertojen määrän.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3Oliko arvo olemassa?
Tarkista jäsenyys hakemalla i bisect_left-funktiolla ja varmistamalla, että a[i] on sama kuin tavoite. Varmista ensin, ettei i saavuta listan pituutta.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xEnsimmäinen vähintään X:n suuruinen alkio
bisect_left löytää myös ensimmäisen alkion, joka on suurempi tai yhtä suuri kuin x. Sen palauttama indeksi osoittaa suoraan alarajan vastaukseen.
i = bisect.bisect_left(a, x) # first >= xEnsimmäinen aidosti suurempi alkio
Tarvitsetko ensimmäisen alkion, joka on aidosti suurempi kuin x? bisect_right antaa indeksin suoraan eli löytää ylärajan vastineen.
i = bisect.bisect_right(a, x) # first > xLisää ja säilytä järjestys
insort etsii paikan ja lisää alkion yhdellä kutsulla, jolloin lista pysyy järjestyksessä. Se on kätevä, kun rakennat järjestettyä rakennetta lennossa.
bisect.insort(a, 5) # a stays sortedHae ikkunan sisältä
Valinnaiset lo- ja hi-argumentit rajoittavat haun osaan listaa. Näin vältyt kopioinnilta, kun tarvitset vain osa-alueen.
bisect.bisect_left(a, x, 2, 5)Avaimet apulistalla
bisect vertaa kokonaisia alkioita, joten jos haluat hakea kentän perusteella, rakenna rinnakkainen lista pelkistä avaimista ja käytä bisect-funktiota siihen.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)Pikatarkistus
Päättele duplikaattien ja lisäyskohtien toiminta.
Kertaus: bisect hallussa
Osaat nyt löytää lisäyskohdat, laskea duplikaatit sekä paikantaa ala- ja ylärajat logaritmisessa ajassa. Käytä bisect-funktiota ennen kuin kirjoitat silmukan. ✨
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
Usein kysytyt kysymykset
Onko oppitunti ”bisect_left ja bisect_right” ilmainen?
Kyllä – oppitunnin ”bisect_left ja bisect_right” 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 ”bisect_left ja bisect_right”?
Etsi lisäyskohdat järjestetystä listasta 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 ”bisect_left ja bisect_right”-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
- Klassinen binäärihaku ilman virheitä
- bisect_left ja bisect_right
- Ensimmäinen True: predikaattibinäärihaku
- Binäärihaku vastauksesta