Att designa en anpassad struktur innebär att kombinera befintliga strukturer så att varje obligatorisk operation når sin målkomplexitet, där en struktur täcker en annan svaghet. Den klassiska tekniken är att para ihop en hash-tabell med en array, heap eller länkad lista.
Ett praktiskt exempel: insert, delete, getRandom — alla O(1)
Krav: insert(x), remove(x) och getRandom() var och en i O(1). En hash-tabell ensam kan inte göra O(1) randomisering; en array ensam kan inte göra O(1) borttagning. Kombinera dem.
import random
class RandomizedSet:
def __init__(self):
self.idx = {} # value -> index in list
self.vals = [] # values for O(1) random pick
def insert(self, x): # O(1)
if x in self.idx: return False
self.idx[x] = len(self.vals)
self.vals.append(x)
return True
def remove(self, x): # O(1): swap with last, pop
if x not in self.idx: return False
i, last = self.idx[x], self.vals[-1]
self.vals[i] = last # move last into the hole
self.idx[last] = i
self.vals.pop()
del self.idx[x]
return True
def getRandom(self): # O(1)
return random.choice(self.vals)
En allmän designrecept
1. List every required operation + its target complexity.
2. For each, name a structure that hits it:
by key O(1) -> hash map
by index O(1) -> array
min/max O(log n) -> heap
ordered O(log n) -> balanced tree / skip list
O(1) splice -> doubly linked list
3. COMBINE them; use the hash map to map keys -> positions/nodes
in the other structure so updates stay O(1).
4. Verify each operation against its target.
| Mönster | Kombinerade strukturer | Möjliggör |
|---|---|---|
| LRU-cache | hash-tabell + dubbelt länkad lista | O(1) get/put |
| O(1) randomiserad mängd | hash-tabell + array | O(1) insert/remove/random |
| Min i O(1) på en stack | stack + hjälpmin-stack | O(1) getMin |
Varför det spelar roll
Riktiga system behöver sällan en enda lärobok-struktur — de behöver en komposit anpassad till ett specifikt åtkomstmönster, vilket är exakt vad dessa designer levererar.
Intervjuare använder dessa problem för att testa om du kan resonera från operationskostnader till en komposition, kärnfärdigheten bakom högtpresterande systemdesign.