|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Schmidt 2:5020/400 15 Feb 2003 00:45:33
To : Aleksey Vaneev
Subject : Re: Максимум в "бегущем окне"
--------------------------------------------------------------------------------
Hello Aleksey,
AV> Задачка такая вылезла. Имеется поток цифр. В каждый момент времени
AV> пополняется одним элементом. Также в каждый момент времени рассматривается
AV> окно, "накрывающее" N прошедших элементов. Дана задача определить в каждый
AV> момент времени максимальную цифру в окне, а также ее индекс. Каким быстрым
AV> способом можно решить эту задачу? Отсортированный динамически изменяющийся
AV> двусвязный список, а также "поголовная" проверка элементов - самые медленные
AV> решения.
Hу вот идейка. Hе знаю уж будет работать иль нет.
Имеем деку. Имеем увеличивающейся на каждом шаге индекс (назовем шаг).
В деке будут сохранятся значения элементов (назову ключ) и
шаг, когда элемент должен быть удален из деки (вследсвии выхода из
окна) назову "время".
Элементы в деке будут всегда отсортированы по ключу, поэтому поиск
двоичный.
Для определенности пусть слева наибольший ключ справа наименьший.
Тогда алгоритм таков:
-если текущий шаг равен "времени" у левого элемента
в деке, то удаляем левый элемент из деки.
- двоичным поиском по "ключу" находим позицию для текущего элемента в деке
и удаляем все элементы правее найденной позиции
- вставляем текущий элемент справа в деку, "время"= текущий шаг + N
- увеличиваем текущий шаг.
Максимальный элемент самый левый в деке. Индекс вычисляется используя
"время" элемента и текущий шаг.
Элементов в деке в среднем будет меньше N. (есди это вовсе будет
работать :-)
Олег.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
