|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
31.03.2008, 16:29 | #1 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
Существование элемента в массиве
Есть последовательность чисел (например, берётся из файла), максимум длины 70000. Числа пронумерованы 1..n. Далее вводятся 3 числа l, r, v. Определить, существует ли v в последовательности от номера l до r (вывести 1) или нет (вывести 0). Нужно осуществить поиск как можно быстрее.
|
31.03.2008, 16:36 | #2 |
Участник клуба
Регистрация: 03.05.2007
Сообщений: 1,189
|
Быстрее чем обычный перебор у тебя ничего не получиться, за исключением случаю, что у тебя массив отсортирован. А так:
ar - это массив куда ты заггрузишь всю последовательность Код:
|
31.03.2008, 16:42 | #3 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
У меня получалось быстрее:
1) пирамидальная сортировка+бинарный поиск. 2) создание бинарного дерева+поиск по дереву 3) разбивал на сегменты с шагом 100 и списком записывал элементы (хорошо только при равномерном разбросе) Только всё по тайм лимиту не влазило. |
31.03.2008, 18:14 | #4 | |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Цитата:
Или метод решения задан и надо обязательно сортировать, а потом искать ? |
|
31.03.2008, 18:17 | #5 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
Вся загвоздка в том, что запросов "Определить, существует ли v в последовательности от номера l до r (вывести 1) или нет (вывести 0)." может быть ОЧЕНЬ много.
|
31.03.2008, 18:33 | #6 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Понял - сортировку делаем один раз при чтении с сохранением индекса. Потом много раз поиск.
А если такой вариант: при чтении формируем элементы: <Число <список позиций, в который встречается> > Элементы сортируем по "Число". Списки позиций сами получится сортированные. Тогда чисел уже будет меньше 70000 - должны же там быть повторы. Кстати, на числа есть какие-то ограничения ? В списке диапазонов ищем позицию. |
31.03.2008, 18:41 | #7 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
0 - 10^9-1
|
31.03.2008, 18:44 | #8 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Этот вариант отпадает. Подумаю.
|
31.03.2008, 18:47 | #9 |
JAVA BEAN
Участник клуба
Регистрация: 22.04.2007
Сообщений: 1,329
|
Можно как вариант:
Но он не прошёл, т.к. числа, похоже, были отсортированы. А можно уравновесить дерево, чтобы для каждого узла слева и справа было примерно одинаковое количество элементов? |
31.03.2008, 18:48 | #10 |
Участник клуба
Регистрация: 12.10.2007
Сообщений: 1,204
|
Ага, это называется сбалансированное дерево.
Вот реализация. Только без удаления узлов. Но, в этом случае удаления не понадобится. Код делал на основе примера из Вирт "Алгоритмы..." Последний раз редактировалось alexBlack; 31.03.2008 в 18:56. |
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Поиск элемента | ЭД4-0014 | Помощь студентам | 12 | 05.06.2008 21:47 |
Как проверить существование потока? | John_chek | Общие вопросы Delphi | 3 | 17.01.2008 15:16 |
создание элемента | Романнн | Общие вопросы Delphi | 6 | 13.12.2007 21:07 |
Проверка на существование | Lonix | Общие вопросы Delphi | 2 | 19.03.2007 19:42 |