|
|
Не совсем в тему, но может быть эта идея поможет вами придумать как за линейное время и медиану найти:
Дано: найти максимально быстро максимум в скользящем окне по некоторой последовательности чисел (для каждого положения окна, окно сдвигается на 1 элемент в одну и ту же сторону на каждом шаге)
Вот алгоритм, сложность которого О(n).
Пусть у нас имеется стек, в котором помимо операций с ВЕРХНИМ элементом, добавлены операции доступа (просмотра и удаления) к НИЖНЕМУ элементу стека. Реализовать такую структуру несложно.
Каждый элемент стека имеет НОМЕР и ВЕС.
В начальный момент времени стек пуст.
Будем считать, что в первый момент времени в окне пусто. Затем в течение m "сдвигов" в окно добавляется по одному числу, а в дальнейшем при каждом сдвиге одно число добавляется, а одно исчезает.
Тогда при каждом сдвиге окна
1. Если НОМЕР нижнего элемента стека равен номеру числа, которое исчезло из окна, удалить этот элемент из стека
2. Создать новый элемент X, номер которого равен порядковому номеру числа, появившегося в окне, а вес - это значение числа, которое появилось в окне
3.
WHILE (стек не пуст и ВЕС верхнего элемента стека меньше ВЕСА элемента X) {
удалить верхний элемент стека
}
4. Поместить элемент Х на верх стека
5. Искомый максимум - это вес нижнего элемента стека
Итого, для последовательности длины n будет сделано n вставок в стек, n удалений из стека и не более 2n сравнений.
PS. Идея любезно предоставлена Sergey_ на форумах сайта algolist.manual.ru
|
|
E-mail: 
info@telesys.ru
