Выбор ответа Senior Задачи на Java обновлено
Выбор структуры по ограничениям
Вопрос
Есть 2·10⁵ операций «добавить число» и «найти наименьшее число, большее x». Какая структура даст нужную скорость?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: TreeSet с методом higher(x): O(log n) на операцию. TreeSet (красно-чёрное дерево) поддерживает вставку и поиск ближайшего за O(log n): суммарно около 4·10⁶ шагов.
Варианты ответа
ArrayListс сортировкой после каждой вставкиHashSetи перебор всех элементов на каждый запросPriorityQueueи методpeek()после каждой вставкиTreeSetс методомhigher(x): O(log n) на операциюправильный ответ
Разбор
TreeSet (красно-чёрное дерево) поддерживает вставку и поиск ближайшего за O(log n): суммарно около 4·10⁶ шагов. Сортировка списка после каждой вставки O(n log n) на операцию. Перебор HashSet O(n) на запрос, итого 4·10¹⁰. PriorityQueue знает только минимум всей кучи, а не наименьший больший x.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.