MiddleКодИногдаЕщё не отвечали

Обернуть почти отсортированный поток чисел в отсортированный

Исходный поток выдаёт положительные числа, смещённые не более чем на k позиций (каждое значение приходит в пределах k от своего отсортированного места); -1 — конец. Спроектируйте SortedStream, оборачивающий источник и выдающий значения по порядку.

Требования:

Тот же интерфейс int get(); -1 означает исчерпание.
Буферизуйте не более k + 1 элементов одновременно.

struct Stream { virtual int get() = 0; };

struct SortedStream : Stream {
    // оборачивает Stream*; ваш код здесь
};

Допишите реализацию.

Держим min-кучу размером не более k + 1. На каждом get дозаполняем её из источника, пока не станет k + 1 элементов или источник не кончится, затем извлекаем наименьший. Значение в пределах k от места, поэтому минимум окна k + 1 — следующий по порядку. Возвращаем -1 при опустошении.

✗Буферизовать весь поток, теряя смысл ограниченной памяти
✗Брать окно размера k вместо k + 1, из-за чего следующий элемент может оказаться меньше
✗Не дренировать буфер после конца источника, теряя хвост

→Почему буфер должен держать k + 1, а не k элементов?
→Какая структура данных даёт здесь O(log k) на извлечение минимума и вставку?

Оглавление

Задача

Спроектируйте SortedStream поверх почти отсортированного потока (смещение до k).

Решение

#include <queue>

struct Stream { virtual int get() = 0; virtual ~Stream() = default; };

struct SortedStream : Stream {
    Stream* src; size_t cap;
    std::priority_queue<int, std::vector<int>, std::greater<int>> buf;  // min-heap
    SortedStream(Stream* s, size_t k) : src(s), cap(k + 1) {}

    int get() override {
        while (buf.size() < cap) {           // дозаполнить окно k+1
            int v = src->get();
            if (v < 0) break;                // источник кончился
            buf.push(v);
        }
        if (buf.empty()) return -1;          // дренаж завершён
        int v = buf.top(); buf.pop();
        return v;
    }
};

Ключевые моменты

Окно k + 1 гарантирует, что минимум в нём — следующий по порядку.
Буферизуем ограниченно, не весь поток.
После конца источника дренируем оставшееся, иначе теряем хвост.

Открыть тему в роадмапе →

Оглавление

MiddleКодИногдаЕщё не отвечали

Обернуть почти отсортированный поток чисел в отсортированный

Требования:

Тот же интерфейс int get(); -1 означает исчерпание.
Буферизуйте не более k + 1 элементов одновременно.

struct Stream { virtual int get() = 0; };

struct SortedStream : Stream {
    // оборачивает Stream*; ваш код здесь
};

Допишите реализацию.

✗Буферизовать весь поток, теряя смысл ограниченной памяти
✗Брать окно размера k вместо k + 1, из-за чего следующий элемент может оказаться меньше
✗Не дренировать буфер после конца источника, теряя хвост

→Почему буфер должен держать k + 1, а не k элементов?
→Какая структура данных даёт здесь O(log k) на извлечение минимума и вставку?

Оглавление

Задача

Спроектируйте SortedStream поверх почти отсортированного потока (смещение до k).

Решение

#include <queue>

struct Stream { virtual int get() = 0; virtual ~Stream() = default; };

struct SortedStream : Stream {
    Stream* src; size_t cap;
    std::priority_queue<int, std::vector<int>, std::greater<int>> buf;  // min-heap
    SortedStream(Stream* s, size_t k) : src(s), cap(k + 1) {}

    int get() override {
        while (buf.size() < cap) {           // дозаполнить окно k+1
            int v = src->get();
            if (v < 0) break;                // источник кончился
            buf.push(v);
        }
        if (buf.empty()) return -1;          // дренаж завершён
        int v = buf.top(); buf.pop();
        return v;
    }
};

Ключевые моменты

Окно k + 1 гарантирует, что минимум в нём — следующий по порядку.
Буферизуем ограниченно, не весь поток.
После конца источника дренируем оставшееся, иначе теряем хвост.

Открыть тему в роадмапе →

Оглавление