Find Median from Data Stream
Zaprojektuj strukturę z dwiema operacjami: addNum przechowuje liczbę całkowitą, a findMedian zwraca medianę wszystkich dotychczas przechowywanych wartości. Mediana przy nieparzystej liczbie wartości to wartość środkowa; przy parzystej liczbie wartości jest to średnia dwóch środkowych wartości.
Operacja i to ops[i], a values[i] zawiera liczbę dla addNum i 0 dla findMedian. Wykonaj je po kolei na pustej strukturze i zwróć po jednym ciągu znaków dla każdej operacji: "null" dla addNum, medianę dla findMedian. Zapisz medianę na przykład jako "3", "2.5" lub "-0.5": bez separatora dziesiętnego dla liczby całkowitej oraz zero jako "0", nigdy jako "-0".
Funkcja
- opsstring-array
- operacje w kolejności, w jakiej są wykonywane
- valuesinteger-array
- liczba dla każdego addNum, 0 dla każdego findMedian
- Zwracastring-array
- jedna odpowiedź na operację, jako tekst
Ograniczenia
1 ≤ ops.length ≤ 3000values.length == ops.length- Każde
ops[i]toaddNumlubfindMedian. -105 ≤ values[i] ≤ 105dlaaddNum, avalues[i] == 0dlafindMedian.findMedianjest wywoływane dopiero po co najmniej jednym wywołaniuaddNum.
Przykłady
- Wejście
- ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
- Wyjście
- ["null", "5", "null", "3", "null", "5", "null", "4"]
- Wyjaśnienie
- Dla 1 i 5 mediana wynosi (1 + 5) / 2 = 3. Dla 1, 5 i 8 wynosi 5, a dla 1, 3, 5 i 8 wynosi (3 + 5) / 2 = 4.
- Wejście
- ops = ["addNum", "addNum", "findMedian", "addNum", "addNum", "findMedian"]values = [-4, 3, 0, -2, -1, 0]
- Wyjście
- ["null", "null", "-0.5", "null", "null", "-1.5"]
- Wyjaśnienie
- -4 i 3 dają w sumie -1, więc mediana wynosi -0.5. Po dodaniu -2 i -1 posortowane wartości to -4, -2, -1, 3; środkowa para daje w sumie -3, więc mediana wynosi -1.5.
Pytanie dodatkowe
Gdyby każda wartość mieściła się w przedziale od 0 do 100, jak można by sprawić, aby obie operacje działały w czasie stałym?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Sortowanie każdej wartości przy każdym wywołaniu
findMedianjest poprawne, ale powoduje powtarzanie wielu operacji. Mediana zależy tylko od środkowych wartości. Które wartości naprawdę musisz szybko znaleźć?Podziel wartości na dolną i górną połowę. Mediana zależy tylko od największej wartości z dolnej połowy i najmniejszej wartości z górnej połowy; kolejność wewnątrz każdej połowy nie ma znaczenia.
Przechowuj dolną połowę w kopcu maksymalnym, a górną połowę w kopcu minimalnym, przy czym dolna połowa powinna zawierać tyle samo wartości co górna lub o jedną więcej. Umieszczaj każdą nową wartość po właściwej stronie, porównując ją z wierzchołkiem dolnej połowy, a następnie przenieś jeden element z wierzchołka, jeśli rozmiary kopców przestaną być odpowiednio zrównoważone.
Rozwiązanie
Mediana znajduje się między dwiema połowami danych, więc kolejność elementów w każdej z nich nie ma znaczenia: liczą się tylko największa wartość z dolnej połowy i najmniejsza z górnej. Dwa kopce utrzymują te dwie wartości na szczycie. Każde addNum kosztuje O(log n), a każde findMedian odczytuje dwie wartości ze szczytów w czasie O(1).
Sortuj przy każdym wywołaniu findMedian
Intuicja
Przechowuj każdą wartość na liście. findMedian sortuje ją i odczytuje indeksy (total-1)/2 oraz total/2, stosując dzielenie całkowite: przy nieparzystej liczbie elementów jest to ten sam indeks, a przy parzystej — para środkowych elementów. Dodaj te dwie wartości i podziel sumę przez dwa, a otrzymasz medianę w obu przypadkach.
Dziel przez dwa, używając liczb całkowitych. Suma parzysta dzieli się bez reszty. Suma nieparzysta daje połowę swojej wartości bezwzględnej, po której następuje .5, ze znakiem sumy, więc -3 daje -1.5.
Każde zapytanie powoduje ponowne sortowanie. Przy 1 500 dodaniach i zapytaniu po każdym z nich oznacza to około 10^7 porównań, podczas gdy kopce wymagają kilkudziesięciu tysięcy kroków.
Algorytm
- Przechowuj listę
values. - Dla
addNum xdopiszxi zapisz"null". - Dla
findMedianposortujvaluesi dodajvalues[(total-1)/2]orazvalues[total/2]. - Podziel sumę przez dwa jako tekst, używając liczb całkowitych, i zapisz ją.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
class MedianFinder:
def __init__(self):
self.values = []
def addNum(self, x):
self.values.append(x)
def findMedian(self):
self.values.sort()
total = len(self.values)
# For an odd count both indexes point at the one middle value.
return half_text(self.values[(total - 1) // 2] + self.values[total // 2])
def medianStreamOps(ops, values):
finder = MedianFinder()
result = []
for op, x in zip(ops, values):
if op == "addNum":
finder.addNum(x)
result.append("null")
else:
result.append(finder.findMedian())
return resultDwa kopce podzielone w medianie
Intuicja
Podziel wartości na dolną połowę low i górną połowę high, tak aby każda wartość w low była mniejsza lub równa każdej wartości w high, a low miała tyle samo elementów co high lub o jeden więcej. Mediana to największa wartość w low, a przy parzystej liczbie wartości — jej średnia z najmniejszą wartością w high. Kopiec maksymalny dla low i kopiec minimalny dla high utrzymują te wartości na wierzchu.
Nowa wartość trafia do low, jeśli jest mniejsza lub równa wartości na jego wierzchu, a w przeciwnym razie do high. Gdy rozmiary przestają być równe, przenieś element z wierzchu jednego kopca do drugiego: to wartość najbliższa drugiej połowie, więc porządek zostaje zachowany. Dodanie wymaga kilku operacji na kopcu, czyli O(log n), lub O(n) w R, gdzie kopiec jest kopiowany przy każdej zmianie.
Po czterech dodaniach z pierwszego przykładu low zawiera 3 i 1, a high zawiera 5 i 8.
Algorytm
- Utrzymuj kopiec maksymalny
lowdla dolnej połowy i kopiec minimalnyhighdla górnej połowy. addNum x: umieśćxwlow, jeślilowjest pusty lubxjest nie większe niż jego wierzchołek; w przeciwnym razie umieść je whigh.- Jeśli
lowzawiera o dwie wartości więcej niżhigh, przenieś wierzchołeklowdohigh. Jeślihighzawiera więcej wartości niżlow, przenieś wierzchołekhighdolow. findMedian: jeślilowjest większy, zapisz jego wierzchołek. W przeciwnym razie dodaj oba wierzchołki i podziel sumę przez dwa, używając dzielenia całkowitoliczbowego.
import heapq
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
class MedianFinder:
def __init__(self):
self.low = [] # the smaller half; heapq is a min-heap, so it stores -x to keep the largest on top
self.high = [] # the larger half, smallest on top
def addNum(self, x):
if not self.low or x <= -self.low[0]:
heapq.heappush(self.low, -x)
else:
heapq.heappush(self.high, x)
# Rebalance: low holds as many values as high, or one more.
if len(self.low) > len(self.high) + 1:
heapq.heappush(self.high, -heapq.heappop(self.low))
elif len(self.high) > len(self.low):
heapq.heappush(self.low, -heapq.heappop(self.high))
def findMedian(self):
if len(self.low) > len(self.high):
return str(-self.low[0])
return half_text(-self.low[0] + self.high[0])
def medianStreamOps(ops, values):
finder = MedianFinder()
result = []
for op, x in zip(ops, values):
if op == "addNum":
finder.addNum(x)
result.append("null")
else:
result.append(finder.findMedian())
return result
Pułapki i przypadki brzegowe
- Wybieranie kopca na podstawie rozmiaru zamiast wartości. Wstawianie elementu do mniejszego kopca bez porównania zaburza kolejność między połówkami, a ich wierzchołki przestają być wartościami środkowymi.
- Dzielenie przez 2 za pomocą zwykłego dzielenia całkowitoliczbowego. W C i Java
-1 / 2wynosi 0, więc dopisanie.5wypisuje 0.5 dla -0.5. W Python-3 // 2wynosi -2, co wypisuje -2.5 dla -1.5. W niektórych językach liczby zmiennoprzecinkowe są wypisywane jako 3.0 lub 2.500000. - Przechowywanie
lowze zmienionym znakiem w kopcu minimalnym i zapominanie o ponownej zmianie znaku podczas odczytu jego wierzchołka lub przenoszenia wartości dohigh. - Wypisywanie
-0. Środkowe wartości -1 i 1 sumują się do 0, a odpowiedzią jest"0".
Najczęstsze pytania3
Jaka jest złożoność czasowa Find Median from Data Stream?
Przy użyciu dwóch kopców addNum ma złożoność O(log n) — najwyżej trzy operacje dodawania lub usuwania elementu z kopca, a findMedian ma złożoność O(1) — dwa odczyty. Przechowywana jest każda wartość, więc złożoność pamięciowa wynosi O(n). Sortowanie przy każdym zapytaniu kosztuje zamiast tego O(n log n) dla każdego wywołania findMedian.
Dlaczego nie przechowywać wartości w posortowanej tablicy?
Posortowana tablica pozwala znaleźć medianę za pomocą findMedian w czasie O(1), a wyszukiwanie binarne znajduje miejsce dla nowej wartości w czasie O(log n). Jednak wstawienie jej przesuwa każdą wartość znajdującą się za tym miejscem, co zajmuje O(n) dla każdego wywołania addNum.
Czy potrafisz znaleźć dokładną medianę strumienia bez przechowywania każdej wartości?
Nie zawsze. Każda z dotychczas zaobserwowanych wartości może później stać się medianą, w zależności od tego, co pojawi się następnie, więc dokładna odpowiedź wymaga uwzględnienia ich wszystkich.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def medianStreamOps(ops, values):
# Wpisz tutaj kodTest #1
Test #2
Argumenty
ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"] values = [5, 0, 1, 0, 8, 0, 3, 0]
Oczekiwany wynik
["null", "5", "null", "3", "null", "5", "null", "4"]