Gruppera och sortera i fack med en map
Gruppera anagram och liknande objekt
Gruppera och sortera i fack med en map är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Gruppering är ett mönster
Många problem ber er att gruppera objekt som har något gemensamt. En koppling från nyckel till behållare gör detta till en enda tydlig genomgång. 🗂️
Välj grupperingsnyckeln
Hela tricket är att välja en nyckel som är identisk för objekt i samma grupp. När detta är rätt blir resten enkelt.
Använd defaultdict som behållare
Använd defaultdict(list) så att varje ny nyckel börjar med en tom behållare. Lägg till objekt utan att någonsin kontrollera om nyckeln finns.
from collections import defaultdict
buckets = defaultdict(list)Den centrala loopen
Beräkna nyckeln för varje objekt och lägg till objektet i nyckelns behållare. En rad per element grupperar allt.
for word in words:
buckets[key_of(word)].append(word)Gruppera anagram
Anagram har samma sorterade bokstäver, så den sorterade strängen är den perfekta gruppnyckeln. Sortera en gång och placera sedan objekten i fack efter den.
k = ''.join(sorted(word))
buckets[k].append(word)Tupelnycklar för räkningar
När sortering går långsamt fungerar en tupel med bokstavsräkningar också som nyckel. Tupler är hashbara och kan därför användas direkt i en dict.
k = tuple(Counter(word)[c] for c in 'abcdefghijklmnopqrstuvwxyz')Placera efter en egenskap
Gruppera tal efter rest, paritet eller längd genom att helt enkelt ändra nyckeln. Mönstret är identiskt i olika problem.
for n in nums:
buckets[n % 3].append(n)Idén bakom bucketsortering
När värdena ryms inom ett litet intervall placerar ni varje värde i ett indexerat fack och läser dem i ordning. Det ger nästan linjär sortering.
for x in nums:
bucket[x].append(x)Samla resultaten
Efter grupperingen är svaret vanligtvis ordbokens values. Konvertera dem till en lista när domaren vill ha själva grupperna.
result = list(buckets.values())Räkna per grupp
Om ni bara behöver gruppernas storlekar kan ni gruppera i en Counter eller summera längderna i slutet. Välj det som faktiskt efterfrågas.
sizes = {k: len(v) for k, v in buckets.items()}Därför vinner mappning
Gruppering med en map tar O(n) i stället för att jämföra varje par. Den hashade nyckeln gör matchningen åt er.
Snabb kontroll
Ni vill gruppera ord så att anagram hamnar i samma behållare.
Sammanfattning
Gruppera genom att koppla varje elements nyckel till en defaultdict-behållare i en enda genomgång på O(n). Välj nyckeln väl, så blir grupperingsproblem mycket enklare. 🚀
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Gruppera och sortera i fack med en map” gratis?
Ja – hela texten till ”Gruppera och sortera i fack med en map” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Gruppera och sortera i fack med en map”?
Gruppera anagram och liknande objekt Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Gruppera och sortera i fack med en map”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Mängder för medlemskap och deduplicering
- Dictionaries som uppslagstabeller
- Counter och defaultdict i praktiken
- Gruppera och sortera i fack med en map