Здравствуйте, pva, Вы писали:

pva>В таком случае мы можем просто разбить весь диаппазон на "окна" размера N и хранить только счетчики для каждого окна при условии что во входящем потоке нет дубликатов.
pva>По входящему индексу просто определяем какому окну принадлежит и увеличиваем там счетчик. По достижению N — выдаем результат.
Да. Гарантия отсутствия дубликатов упрощает алгоритм.
Update: Нужно быть аккуратным, и всё же держать очередь окон. Иначе есть риск первым собрать полный комплект не от "текущего" окна, а от "следующего" — тогда наивный алгоритм отправит сначала "следуюшее" окно, а уже потом — предыдущее.
В остальном, всё остаётся вполне простым.