DSU med path compression
Find og foren på næsten konstant tid
DSU med path compression er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad en DSU holder styr på
En Disjoint Set Union holder elementer samlet i ikke-overlappende mængder, så du kan spørge, om to ting allerede hører sammen. 🤝
Mængder som træer
DSU gemmer hver mængde som et træ. Hvert element peger på en forælder, og den øverste node, roden, er det entydige navn for hele gruppen.
Forælder-arrayet
Du gemmer alle disse forbindelser i ét array. Start med hvert element som sin egen forælder, hvilket betyder, at hvert element begynder i sin egen mængde.
parent = list(range(n))Find roden
Operationen find følger forælderforbindelserne opad, indtil et element peger på sig selv. Den node, der peger på sig selv, er roden, som identificerer mængden.
while parent[x] != x:
x = parent[x]Lange kæder er et problem
Uden omtanke kan mængder danne lange, smalle kæder. Så gennemgår find noderne én efter én, og en enkelt forespørgsel kan koste O(n), hvilket er alt for langsomt.
Indfør stikomprimering
Stikomprimering løser dette: Mens du finder roden, lader du alle besøgte noder pege direkte på roden, så træet bliver fladere til næste gang. ⚡
Rekursiv komprimering
Den enkleste måde er rekursion. Find roden, og gem den derefter tilbage i parent[x], før du returnerer, så forbindelsen forkortes permanent.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]To elementer, samme mængde?
Hvis du vil kontrollere, om to elementer er forbundet, sammenligner du deres rødder. Hvis find(a) er lig med find(b), er de i samme gruppe; ellers er de stadig adskilt.
if find(a) == find(b):
print("connected")Sammenføj to mængder
Operationen union sammenføjer grupper ved at lade den ene rod pege på den anden. Én linje forbinder to hele træer til én enkelt mængde.
def union(a, b):
parent[find(a)] = find(b)Hvorfor det er så hurtigt
Med komprimering alene kører operationerne omtrent i O(log n) amortiseret tid, og sammen med rangordning når de næsten konstant tid pr. forespørgsel.
Hvor DSU er særlig nyttig
DSU løser spørgsmål om sammenhæng: vennekredse, netværkskomponenter og Kruskals udspændende træ bygger alle på hurtig find og union. 🌐
Hurtigt tjek
Tænk over, hvad stikomprimering faktisk ændrer.
Opsummering
Du byggede en DSU: et forælder-array, find til at hente roden og union til at sammenføje. Stikomprimering holder den lynhurtig. Godt arbejde! 🎉
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “DSU med path compression” gratis?
Ja — hele teksten til “DSU med path compression” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “DSU med path compression”?
Find og foren på næsten konstant tid Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “DSU med path compression”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- DSU med path compression
- Union by rank og komponenter
- Kruskals minimum spanning tree
- Prims MST med en heap