Kth Largest Element in a Stream

Q: Dlaczego do znalezienia k-tego największego elementu używamy kopca minimalnego, a nie maksymalnego?

Najmniejsza z k największych wartości jest zarówno odpowiedzią, jak i wartością, którą musi przebić nowa osoba, a kopiec minimalny o rozmiarze k utrzymuje ją na szczycie. Kopiec maksymalny zawierający wszystkie wartości umieszcza największą z nich na szczycie, więc aby dotrzeć do k -tej, trzeba usuwać k-1 wartości i wstawiać je z powrotem po każdym przybyciu.

Q: Jaka jest złożoność czasowa problemu znalezienia k-tego największego elementu w strumieniu?

Każde dodanie elementu kosztuje O(log k) : jedno porównanie z elementem na szczycie i co najwyżej jedno przesiewanie w kopcu zawierającym k wartości. Zbudowanie kopca z nums kosztuje O(n log k) , więc całe działanie zajmuje O((n + m) log k) czasu i wymaga O(k) dodatkowej przestrzeni.

ŁatweKopiec

+10

Strumień liczb całkowitych zaczyna się od wartości w nums. Następnie wartości z adds napływają pojedynczo. Po każdym napływie zapisz k-tą największą wartość spośród wszystkich dotychczasowych, licząc osobno równe wartości. Zwróć zapisane wartości w kolejności, po jednej dla każdej wartości z adds.

nums zawiera co najmniej k-1 wartości, więc po pierwszym napływie zawsze jest co najmniej k wartości do wyboru.

Funkcja

kthLargestStream(k: integer, nums: integer-array, adds: integer-array) → integer-array

kinteger: ranga do zgłoszenia, 1 dla największej wartości
numsinteger-array: wartości już znajdujące się w strumieniu
addsinteger-array: wartości, które przychodzą, w kolejności
Zwracainteger-array: k-ta największa wartość po każdym nowym elemencie

Ograniczenia

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums mogą być w dowolnej kolejności, a równe wartości są liczone jako osobne wartości.

Przykłady

Wejście: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
Wyjście: [3, 5, 6, 6, 7]
Wyjaśnienie: Po 3 pojawia się trzecia co do wielkości liczba spośród 7, 5, 3 i 1: 3. Następnie 9 podnosi ją do 5, 6 podnosi ją do 6, 2 niczego nie zmienia, a 8 podnosi ją do 7 (9, 8, 7).

Wejście: k = 1nums = [-2]adds = [-5, 0, -1, 4]
Wyjście: [-2, 0, 0, 4]
Wyjaśnienie: Dla k = 1 odpowiedzią jest największa dotychczasowa wartość: -2, dopóki nie pojawi się 0, nadal 0 po -1, a następnie 4.

Pytanie dodatkowe

Jak odpowiedziałbyś na to samo pytanie, gdyby wartości można było również usuwać ze strumienia?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Wartości nigdy nie opuszczają strumienia, więc wartość, która spadnie poniżej obecnej k-tej największej, wypada na dobre. Zachowuj tylko k największych wartości w kopcu minimum: jego wierzchołek jest odpowiedzią, a każde pojawienie się wartości wymaga jednego porównania i co najwyżej jednej aktualizacji kopca w czasie O(log k).

Sortuj po każdym przybyciu

Poprawne, ale nie kończy się na największych testach

Intuicja

Przechowuj każdą wartość na liście. Po każdym dodaniu posortuj ją rosnąco i odczytaj indeks length-k, czyli z definicji k-tą największą wartość.

Każde dodanie wymaga posortowania maksymalnie n + m wartości, gdzie n i m to długości nums i adds. Przy 10^4 elementach w każdej z nich daje to łącznie około 2 × 10^9 porównań.

Algorytm

Skopiuj nums do listy values.
Dla każdej wartości z adds dodaj ją na końcu values.
Posortuj values rosnąco i zapisz values[length-k].
Zwróć zapisane wartości.

def kthLargestStream(k, nums, adds):
    values = list(nums)
    result = []
    for x in adds:
        values.append(x)
        values.sort()
        # In increasing order the k-th largest sits k places from the end.
        result.append(values[len(values) - k])
    return result

Min-kopiec zawierający k największych wartości

Intuicja

Gdy nad daną wartością pojawi się k większych wartości, pozostanie tak już do końca strumienia, więc liczy się tylko k największych wartości dotychczas. Przechowuj je w kopcu minimalnym. Jego wierzchołek to najmniejsza z k największych wartości, czyli dokładnie k-ta największa wartość w całym zbiorze.

Gdy pojawi się x, a kopiec jest pełny, porównaj ją z wartością na wierzchołku. Jeśli x nie jest większa, nie należy do k największych wartości i nic się nie zmienia. Jeśli jest większa, wartość z wierzchołka wypada: zastąp ją przez x i przesiej w dół w czasie O(log k). Wartości początkowe przechodzą przez tę samą procedurę, więc nums może zawierać więcej niż k elementów.

W pierwszym przykładzie po przetworzeniu nums kopiec zawiera 7, 1 i 5, a na wierzchołku znajduje się 1. Pojawienie się 3 powoduje zastąpienie 1, a wartość na wierzchołku, 3, jest pierwszą odpowiedzią.

Algorytm

Rozpocznij od pustego kopca minimalnego.
Aby dodać x: jeśli kopiec zawiera mniej niż k wartości, wstaw x. W przeciwnym razie, jeśli x jest większe od elementu na szczycie, zastąp nim element na szczycie i przywróć porządek kopca.
Dodaj w ten sposób każdą wartość z nums.
Dla każdej wartości z adds dodaj ją i zapisz element ze szczytu kopca.
Zwróć zapisane wartości.

import heapq


def kthLargestStream(k, nums, adds):
    # A min-heap of the k largest values so far; heap[0] is the smallest of them.
    heap = []

    def add(x):
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x

    for x in nums:
        add(x)
    result = []
    for x in adds:
        add(x)
        result.append(heap[0])  # the k-th largest so far
    return result

Pułapki i przypadki brzegowe

Usuwanie duplikatów. Cztery największe wartości spośród 9, 6, 6, 6, 2 to 9, 6, 6 i 6. Zbiór lub sprawdzanie, które pomija wartości już obecne, zwraca 2 zamiast 6 w trzecim przykładzie.
Odczytywanie odpowiedzi przed dodaniem. Gdy nums zawiera k-1 wartości, kopiec jest pełny dopiero po pierwszym dodaniu, więc najpierw dodaj wartość, a potem odczytaj element ze szczytu.
Liczenie od niewłaściwego końca po sortowaniu. W kolejności rosnącej k-ta największa wartość znajduje się pod indeksem length-k; indeks k-1 zawiera k-tą najmniejszą wartość.
Przyjmowanie domyślnego porządku kopca. priority_queue w C++ i BinaryHeap w Rust to kopce maksymalne: przekaż greater<int> lub opakuj wartości w Reverse.

Najczęstsze pytania3

Dlaczego do znalezienia k-tego największego elementu używamy kopca minimalnego, a nie maksymalnego?

Najmniejsza z k największych wartości jest zarówno odpowiedzią, jak i wartością, którą musi przebić nowa osoba, a kopiec minimalny o rozmiarze k utrzymuje ją na szczycie. Kopiec maksymalny zawierający wszystkie wartości umieszcza największą z nich na szczycie, więc aby dotrzeć do k-tej, trzeba usuwać k-1 wartości i wstawiać je z powrotem po każdym przybyciu.

Jaka jest złożoność czasowa problemu znalezienia k-tego największego elementu w strumieniu?

Każde dodanie elementu kosztuje O(log k): jedno porównanie z elementem na szczycie i co najwyżej jedno przesiewanie w kopcu zawierającym k wartości. Zbudowanie kopca z nums kosztuje O(n log k), więc całe działanie zajmuje O((n + m) log k) czasu i wymaga O(k) dodatkowej przestrzeni.

Czy K-ty największy element w strumieniu można znaleźć za pomocą posortowanej listy?

Tak. Utrzymuj wszystkie wartości w porządku rosnącym, wstawiaj każdą nową wartość na właściwe miejsce za pomocą wyszukiwania binarnego i odczytuj wartość znajdującą się k miejsc od końca. Wyszukiwanie ma złożoność O(log n), ale przesuwanie wartości po miejscu wstawienia ma złożoność O(n) dla każdej nowej wartości: około 1.5 × 10^8 przesunięć dla 10^4 wartości początkowych i 10^4 nowych wartości.

def kthLargestStream(k, nums, adds):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

k = 3
nums = [7, 1, 5]
adds = [3, 9, 6, 2, 8]

Oczekiwany wynik

[3, 5, 6, 6, 7]