Kth Largest Element in a Stream

Q: Почему для k-го по величине элемента используют мин-кучу, а не макс-кучу?

Наименьшее из k наибольших значений — это и ответ, и значение, которое должен превзойти новичок; min-heap размера k держит его на вершине. max-heap из всех значений держит на вершине наибольшее значение, поэтому, чтобы добраться до k -го, нужно извлекать k-1 значений и возвращать их в кучу при каждом поступлении нового значения.

Q: Какова временная сложность задачи «K-й по величине элемент в потоке»?

Каждое добавление требует O(log k) : одного сравнения с вершиной и не более одного просеивания через кучу из k значений. Построение кучи из nums требует O(n log k) , поэтому весь запуск занимает O((n + m) log k) времени и O(k) дополнительной памяти.

ЛегкоКуча

+10

Поток целых чисел начинается со значений в nums. Затем значения из adds поступают по одному. После каждого поступления записывай k-е по величине значение среди всех увиденных к этому моменту, считая равные значения отдельно. Верни записанные значения в том же порядке — по одному для каждого значения из adds.

В nums содержится как минимум k-1 значений, поэтому после первого поступления всегда будет как минимум k значений на выбор.

Функция

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

kinteger: ранг для вывода: 1 — для наибольшего значения
numsinteger-array: значения, уже находящиеся в потоке
addsinteger-array: значения, которые поступают, по порядку
Возвращаетinteger-array: k-е наибольшее значение после каждого поступления

Ограничения

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums может быть в любом порядке, а одинаковые значения считаются отдельными значениями.

Примеры

Ввод: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
Вывод: [3, 5, 6, 6, 7]
Пояснение: После 3 идёт третье по величине число среди 7, 5, 3 и 1 — это 3. Затем 9 поднимает его до 5, 6 — до 6, 2 ничего не меняет, а 8 поднимает его до 7 (9, 8, 7).

Ввод: k = 1nums = [-2]adds = [-5, 0, -1, 4]
Вывод: [-2, 0, 0, 4]
Пояснение: При k = 1 ответом является наибольшее на данный момент значение: -2, пока не появится 0; после -1 всё ещё 0, затем 4.

Дополнительный вопрос

Как бы ты ответил на тот же вопрос, если бы значения также можно было удалять из потока?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Значения никогда не покидают поток, поэтому значение, которое становится меньше текущего k-го наибольшего, уже не вернётся. Храните только k наибольших значений в минимальной куче: её вершина — это ответ, а при поступлении каждого значения требуется одно сравнение и не более одного обновления кучи за O(log k).

Сортируйте после каждого прибытия

Верно, но не успевает на самых больших тестах

Идея

Храните каждое значение в списке. После каждого добавления сортируйте его по возрастанию и считывайте элемент с индексом length-k — по определению это k-е по величине значение.

При каждом добавлении сортируются до n + m значений, где n и m — длины nums и adds. Если каждого из них по 10^4, всего получится около 2 × 10^9 сравнений.

Алгоритм

Скопируй nums в список values.
Для каждого значения из adds добавь его в values.
Отсортируй values по возрастанию и сохрани values[length-k].
Верни сохранённые значения.

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

Мин-куча из k наибольших значений

Идея

Как только у значения появляется k больших значений выше него, это остаётся верным до конца потока, поэтому имеют значение только k наибольших значений, встреченных к этому моменту. Храните их в мин-куче. Её вершина — наименьшее из k наибольших значений, то есть ровно k-е наибольшее значение в целом.

Когда поступает x и куча заполнена, сравните его с вершиной. Если x не больше, оно не входит в k наибольших значений, и ничего не меняется. Если оно больше, вершина выбывает: замените её на x и выполните просеивание вниз за O(log k). Начальные значения проходят ту же процедуру, поэтому nums может быть длиннее k.

В первом примере после обработки nums в куче находятся 7, 1 и 5, причём на вершине стоит 1. Поступившее значение 3 заменяет 1, а вершина — 3 — становится первым ответом.

Алгоритм

Начните с пустой минимальной кучи.
Чтобы добавить x: если в куче меньше k значений, добавьте x. Иначе, если x больше верхнего элемента, замените верхний элемент на x и восстановите порядок кучи.
Добавьте таким образом каждое значение из nums.
Для каждого значения из adds добавьте его и запишите верхний элемент кучи.
Верните записанные значения.

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

Ловушки и крайние случаи

Удаление дубликатов. Четыре наибольших числа среди 9, 6, 6, 6, 2 — это 9, 6, 6 и 6. Множество или проверка, пропускающая уже имеющиеся значения, вернёт 2 в третьем примере вместо 6.
Чтение ответа перед добавлением. Когда nums содержит k-1 значений, куча заполняется только после первого добавления, поэтому сначала добавьте элемент, а затем прочитайте верхний.
Подсчёт не с того конца после сортировки. При сортировке по возрастанию k-е наибольшее число находится по индексу length-k; по индексу k-1 находится k-е наименьшее.
Использование порядка кучи по умолчанию. priority_queue в C++ и BinaryHeap в Rust — это максимальные кучи: передайте greater<int> или оберните значения в Reverse.

Частые вопросы3

Почему для k-го по величине элемента используют мин-кучу, а не макс-кучу?

Наименьшее из k наибольших значений — это и ответ, и значение, которое должен превзойти новичок; min-heap размера k держит его на вершине. max-heap из всех значений держит на вершине наибольшее значение, поэтому, чтобы добраться до k-го, нужно извлекать k-1 значений и возвращать их в кучу при каждом поступлении нового значения.

Какова временная сложность задачи «K-й по величине элемент в потоке»?

Каждое добавление требует O(log k): одного сравнения с вершиной и не более одного просеивания через кучу из k значений. Построение кучи из nums требует O(n log k), поэтому весь запуск занимает O((n + m) log k) времени и O(k) дополнительной памяти.

Можно ли найти K-й наибольший элемент в потоке с помощью отсортированного списка?

Да. Поддерживай значения отсортированными, вставляй каждое новое значение на своё место с помощью бинарного поиска и считывай значение, отстоящее на k позиций от конца. Поиск занимает O(log n), но сдвиг значений после места вставки занимает O(n) на каждое новое значение: около 1.5 × 10^8 сдвигов для 10^4 исходных значений и 10^4 новых значений.

def kthLargestStream(k, nums, adds):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

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

Ожидаемый вывод

[3, 5, 6, 6, 7]