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

Question

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

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

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

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

Answer 1

Подводя итог, у вас есть следующие опции:

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

Выберите одну.Там нет никакого способа сделать то, что вы хотите в O (N) времени без дополнительной памяти.

Answer 2

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

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

• Итерация по массиву
• Для каждого членаищите повторы, удаляйте их.

В худшем случае сложность сценария O (n ^ 2)

Answer 3

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

Вы можете переопределить вставку объекта, чтобы предотвратить вставку повторяющихся элементов.Это 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 триллион узлов, так что это огромный объем дополнительной памяти.Сохраняя несколько значений для каждого узла (а в вышеупомянутом случае каждый узел фактически является частичным значением и другим деревом), мы можем значительно уменьшить объем памяти, но при этом иметь впечатляющую производительность.

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

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

Так что, если вы имеете дело с большими наборами данных, это не является большой проблемой для производительности и памяти.По сути, как вы, наверное, знаете, когда один поднимается, другой падает.Multitree, своего рода найти оптимальную среду.(при условии, что вы правильно выбрали размеры узлов)

---

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

Answer 4

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