Вставка в отсортированный список, в постоянное время

У меня есть отсортированный список целых чисел, и я хочу вставить в этот список любой элемент в постоянное время. Мне разрешено выполнять предварительную обработку, если она позволит мне запускать эту операцию в постоянное время (то есть независимо от того, сколько раз я повторяю эту операцию после предварительной обработки, она должна работать в постоянное время).Вставка в отсортированный список, в постоянное время

Как это можно сделать?

Edit: я могу думать о еще пару ограничений, чтобы сделать его немного менее двусмысленными, и немного более сложным, чтобы решить -

список должен быть сохранен в отсортированном порядке после вставки (s)
Или список должен каким-то образом поддерживать максимальные/минимальные операции в посто нном вводе времени.

источник

2014-10-14 aspen100

Check [этот ответ] (http://stackoverflow.com/a/1933099/115272) –

Если диапазон ваших целочисленных значений невелики. - вы можете использовать ведро за целое значение При. вставьте значение, вы просто индексируете в ведро значение (постоянное время) и добавляете его в ведро (также постоянное время). –

Джейкоб, это только O (1), когда вы знаете, куда вы хотите вставить. (n) на эту позицию. Джейсон, это не плохо bu t «любой элемент» в вопросе кажется немного тревожным - диапазон может не быть ограниченным. – paxdiablo

Вы можете поместить целые числа в radix tree, рассматривая целые числа как битовые строки. С радиусом 2 и списком 32-битных целых чисел у вас будет максимальная глубина дерева 32, что является вашим постоянным фактором для вставки в постоянное время (вы обычно не делали бы что-то вроде этого, потому что постоянный коэффициент для дерево оснований, вероятно, будет больше, чем лог-фактор сбалансированного двоичного дерева, плюс все биты, которые вам нужно будет сделать для дерева оснований, будут дорогостоящими)

источник

2014-10-14 02:23:50

Это не так уж плохо, я думаю, что это редкий массив 4G. Вы также можете иметь каждый узел, содержащий подсчет, чтобы обслуживать дубликаты. – paxdiablo

+1 для того, чтобы думать об этом как битовые строки. Никогда бы так и не подошел. – aspen100

@ aspen100 Вы также можете использовать шестнадцатеричные строки, чтобы уменьшить глубину дерева –

Используйте LinkedHashMap. Определите, сколько элементов хранится на хэш-код (скажем, целые числа 0-10 являются хэш (1), целые числа 11-20 являются хэш (2) и т. Д.)

Когда вы читаете целое число, вычислите его хэш O (1) -> получить доступ к хэш-карте (примерно O (1)) -> вставить в список как первый элемент O (1). Если вы хотите, чтобы дубликаты расширяли каждый элемент в списке в свой собственный список или использовали счетчик для каждого элемента.

источник

2014-10-14 02:33:26

- достаточно хорошее решение для большинства случаев, но что, если диапазон целых чисел неизвестен? это все еще постоянное время? – aspen100

Да, поскольку любое целое число, вы вставляете его в начало связанного списка, так что его O (1) –

Нет, потому что тогда вы нарушаете отсортированный порядок списка. Проблема сложнее делать в O (1) время, когда вы хотите сохранить список, и поддерживать другие операции, такие как max/min, в постоянное время, но также, но ваши решения достаточны, если размер ковша не находится в пределах порядков величины размера проблемы. – aspen100

Ускоренное управление принимает O (log (log (M)) время для операций вставки/удаления/поиска, где M - максимальное значение в подлежащем хранению домене. Емкость пространства равна O (n).

http://en.wikipedia.org/wiki/Y-fast_trie

источник

2014-10-14 07:51:36 Dave

Вставка в отсортированный список, в постоянное время

ответ

Смежные вопросы