Как удалить дубликаты из массива без сортировки

Question

У меня есть массив, который может содержать повторяющиеся объекты. Интересно, можно ли найти и удалить дубликаты в массиве: - без сортировки (строгое требование) - без использования временного вторичного массива - возможно в O (N), с N nb элементов в массив

В моем случае массив представляет собой массив Lua, который содержит таблицы:

t={ 
{a,1}, 
{a,2}, 
{b,1}, 
{b,3}, 
{a,2} 
} 

В моем случае, т [5] является дубликатом т [2], а т [1] не ,

Answer 1

Итак, у вас есть следующие варианты:

• время: O (N^2), не хватает памяти - для каждый элемент массива ищет равный один линейный
• время: O (n * log n), без дополнительной памяти - сортировать сначала, линейно перемещаться по массиву после
• время: O (n), память: O (n) - использовать таблицу поиска (изменить: это, вероятно, не вариант в виде таблицы s не могут быть ключами в других таблицах, насколько я помню)

Выберите один. Невозможно делать то, что вы хотите в O (n), без дополнительной памяти.

Answer 2

Итерируйте массив, придерживайте каждое значение в хэше, проверяя, существует ли оно первым. Если он удаляет исходный массив (или не записывать на новый). Не очень эффективна память, но только 0 (n), так как вы только повторяете массив один раз.

Answer 3

не может быть сделано в O (N), но ...

, что вы можете сделать, это

• итерацию через массив
• Для каждого поиска членов вперед для повторов, удалить те, ,

Худшие сложность случае сценарий O (N^2)

Answer 4

Да, в зависимости от того, как вы на это смотрите.

Вы можете переопределить вставку объекта, чтобы предотвратить вставку повторяющихся элементов. Это O (n) для каждой вставки объекта и может быстрее реагировать на меньшие массивы.

Если вы предоставляете сортировку и удаление объектов, то это O (log n). По существу, вы всегда держите список отсортированным, как вы вставляете и удаляете, так что поиск элементов - это двоичный поиск. Стоимость здесь заключается в том, что поиск элементов теперь O (log n) вместо O (1).

Это также может быть эффективно реализовано с использованием таких вещей, как красно-черное дерево и многопользовательский режим, но за счет дополнительной памяти. Такие реализации предлагают несколько преимуществ для определенных проблем. Например, у нас может быть тип поведения O (log n) даже очень очень больших таблиц с небольшим небольшим объемом памяти, используя вложенное дерево. Дерево верхнего уровня предоставляет своего рода спаренный обзор набора данных, в то время как поддеревы обеспечивают более совершенный доступ, когда это необходимо.

Например, чтобы увидеть это, у нас есть N элементов. Мы могли бы разбить это на группы n1.Затем каждая из этих групп может быть разделена на n2 группы и группы в группы n2. Следовательно, мы имеем глубину N/n1n2 ...

Как вы можете видеть, продукт n может стать довольно огромным очень быстро даже для небольших n. Если N = 1 триллион элементов и n1 = 1000, n2 = 1000, n3 = 1000, то для каждого времени доступа требуется только 1000 + 1000 + 1000 + 1000 с = 4000. Кроме того, мы имеем всего 10^9 раз на каждый узел памяти.

Сравните это со средним 500-миллиардным временем доступа, необходимым для прямого линейного поиска. Это более чем в 100 миллионов раз быстрее и в 1000 раз меньше памяти, чем двоичное дерево, но примерно в 100 раз медленнее! (конечно, есть некоторые накладные расходы, чтобы сохранить согласованное дерево, но даже это можно уменьшить).

Если бы мы использовали двоичное дерево, тогда он имел бы глубину около 40. Проблема состоит в том, что около 1 триллиона узлов, что является огромным объемом дополнительной памяти. Сохраняя несколько значений для каждого узла (и в приведенном выше случае каждый узел фактически является частичным значением и другим деревом), мы можем значительно уменьшить объем памяти, но при этом иметь впечатляющую производительность.

По существу линейный доступ преобладает при более низких числах и преобладает преобладание деревьев при высоких количествах. Дерева. Дерево потребляет больше памяти. Используя multitree, мы можем комбинировать лучшее из обоих миров, используя линейный доступ к меньшим числам и имея большее количество элементов на узел (по сравнению с бинарным деревом).

Такое дерево не являются тривиальными, чтобы создать, но по существу следовать той же алгоритмический характер стандартного двоичного дерева, красно-черный дерева, AVL дерева, и т.д. ...

Итак, если вы имеете дело с большими наборами данных не огромная проблема для производительности и памяти. По сути, как вы, вероятно, знаете, как один идет вверх, другой идет вниз. Multitree's, вид поиска оптимальной среды. (Если вы выбрали ваши размеры узла правильно)

---

Глубина в multitree является N/продукт (n_k, к = 1..m). Объем памяти - это количество узлов, которые являются продуктом (n_k, k = 1..m) (который обычно можно уменьшить на порядок или, возможно, n_m)