Предположим , что мы читаем последовательность чисел, один за другим. Как найти к «й наименьший элемент только с помощью O ( K ) клеток памяти и в линейном времени ( O ( п ) ). Я думаю , что мы должны сохранить первые K члены последовательности и когда получим K + 1 «й член, удалить термин , который мы уверены , что она не может стать к » й наименьший элемент , а затем сохранить к + 1 «й член. Таким образом, у нас должен быть индикатор, который показывает этот непригодный термин на каждом шаге, и этот индикатор должен быстро обновляться на каждом шаге. Я начал с «Макс»; но он не может обновить быстро; Значит , что если мы будем рассматривать не более , то в первом делеции мы пропускаем макс , и мы должны искать максимум в и его причины ( п - к ) × O ( к ) время , что это не линейная. Может быть , мы должны сохранить первые K член последовательности более разумно.
Как мне решить эту проблему?
источник
Ответы:
Создайте буфер размером . Прочитать в 2 k элементов из массива. Используйте алгоритм выбора линейного времени, чтобы разделить буфер так, чтобы k наименьших элементов были первыми; это занимает O ( K ) время. Теперь прочитайте еще k элементов из вашего массива в буфер, заменив k самых больших элементов в буфере, разделите буфер, как и раньше, и повторите.2k 2k k O(k) k k
Для этого требуется времени и O ( k ) пространства.O(k∗n/k)=O(n) O(k)
источник
min
источник