Inversjoner med en BIT
Tell par som står i feil rekkefølge, effektivt
Inversjoner med en BIT er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva er en inversjon
En inversjon er et par i < j der a[i] > a[j]. Det er ett par som står i feil rekkefølge, og å telle dem måler hvor usortert et array er.
Hvorfor inversjoner er viktige
Antallet inversjoner er likt antallet bytter en boblesortering ville gjort. Konkurranseoppgaver skjuler dette ofte i spørsmål om rangering og uorden.
Den naive opptellingen er for treg
Å sjekke hvert par er O(n^2). For n rundt 100000 betyr det ti milliarder sjekker, langt over tidsgrensen. Vi trenger noe smartere. 🐢
BIT-idéen
Gå gjennom arrayet fra venstre mot høyre og spør: Hvor mange tidligere elementer er større enn det nåværende? Et Fenwick-tre svarer på dette underveis.
Tell etter frekvens
BIT-en lagrer en frekvenstabell over verdiene. update(v, 1) registrerer at verdien v har forekommet så langt i gjennomgangen.
update(v, 1)Større verdier betyr et suffiks
Tidligere verdier som er større enn v, er antallet observerte minus antallet som er mindre enn eller lik v. Det er i minus query(v) for det i-te elementet.
inv += i - query(v)Koordinatkomprimering
Hvis verdiene er store eller negative, mapper du dem først til rangeringer fra 1..n. Denne komprimeringen holder BIT-en liten uten å endre rekkefølgen.
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}Hele gjennomgangen
Gå gjennom arrayet, legg hvert antall større verdier til totalen, og sett deretter inn den nåværende verdien. Den løpende totalen er inversjonstallet ditt.
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)Det kjører på n log n
Hvert element utløser én spørring og én oppdatering, begge på O(log n). Hele opptellingen blir ferdig på O(n log n)-tid. 🚀
Flettesortering er slektningen
Flettesortering teller også inversjoner på O(n log n) under flettingen. BIT-versjonen er ofte kortere å skrive under tidspress.
Pass på heltallsoverløp
Antallet inversjoner kan nå omtrent n i andre delt på to, noe som er enormt. Python-heltall har ubegrenset størrelse, men i andre språk trenger du en type på 64 bit.
Rask sjekk
Test hvor godt du forstår kostnaden ved gjennomgangen.
Oppsummering: Tell uorden
Du telte inversjoner på O(n log n) ved å gå fra venstre mot høyre og spørre en BIT hvor mange større verdier som kom tidligere. Komprimer verdiene ved behov. ✅
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Inversjoner med en BIT» gratis?
Ja – hele teksten i «Inversjoner med en BIT» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Inversjoner med en BIT»?
Tell par som står i feil rekkefølge, effektivt Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Inversjoner med en BIT»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Fenwick-tre for prefikssummer
- Inversjoner med en BIT
- Segmenttre: bygg og spør
- Lat oppdatering for intervalloppdateringer