Массив удаляет дублирующиеся элементы
У меня есть неотсортированный массив, что лучший метод должен удалить все дубликаты элемента если существующий?
например:
a[1,5,2,6,8,9,1,1,10,3,2,4,1,3,11,3]
таким образом, после той операции массив должен быть похожим
a[1,5,2,6,8,9,10,3,4,11]
6 ответов
Сверять каждый элемент с каждым другим элементом
Наивное решение состоит в том, чтобы сравнивать каждый элемент с каждым другим элементом. Это расточительно и дает решение O (n 2 ), даже если вы идете только «вперед».
Сортировка, затем удаление дубликатов
Лучшее решение - отсортировать массив, а затем проверить каждый элемент рядом с ним, чтобы найти дубликаты. Выберите эффективную сортировку, и это O (n log n).
Недостатком решения на основе сортировки является то, что порядок не поддерживается. Однако об этом может позаботиться дополнительный шаг. Поместите все записи (в уникальном отсортированном массиве) в хеш-таблицу с доступом O (1). Затем перебрать исходный массив. Для каждого элемента проверьте, есть ли он в хеш-таблице. Если это так, добавьте его к результату и удалите из хеш-таблицы. В результате вы получите результирующий массив, который имеет порядок оригинала, где каждый элемент находится в той же позиции, что и его первое вхождение.
Линейные виды целых чисел
Если вы имеете дело с целыми числами некоторого фиксированного диапазона, вы можете добиться большего, используя сортировку по основанию. Если вы предположите, что все числа находятся в диапазоне от 0 до 1 000 000, например, вы можете выделить битовый вектор примерно 1 000 001.Для каждого элемента в исходном массиве вы устанавливаете соответствующий бит на основе его значения (например, значение 13 приводит к установке 14-го бита). Затем просмотрите исходный массив, проверьте, находится ли он в битовом векторе. Если это так, добавьте его в массив результатов и удалите этот бит из битового вектора. Это O (n) и меняет пространство на время.
Решение с хеш-таблицей
Это приводит нас к лучшему из всех решений: сортировка на самом деле отвлекает, хотя и полезна. Создайте хеш-таблицу с доступом O (1). Просмотрите исходный список. Если его еще нет в хеш-таблице, добавьте его в массив результатов и добавьте в хеш-таблицу. Если он есть в хеш-таблице, игнорируйте его.
Это, безусловно, лучшее решение. Так почему остальные? Потому что проблемы, подобные этой, связаны с адаптацией знаний, которые у вас есть (или должны быть), к проблемам и их уточнению на основе предположений, которые вы делаете для решения. Разработка решения и понимание стоящих за ним идей гораздо полезнее, чем выдумка решения.
Кроме того, хеш-таблицы не всегда доступны. Возьмем встроенную систему или что-то еще, где ОЧЕНЬ ограничено место. Вы можете реализовать быструю сортировку по горстке кодов операций, гораздо меньше, чем может быть любая хеш-таблица.
Если вам не нужно сохранять исходный объект, вы можете зациклить его и создать новый массив уникальных значений. В C # используйте список, чтобы получить доступ к требуемой функциональности. Это не самое привлекательное или разумное решение, но оно работает.
int[] numbers = new int[] {1,2,3,4,5,1,2,2,2,3,4,5,5,5,5,4,3,2,3,4,5};
List<int> unique = new List<int>();
foreach (int i in numbers)
if (!unique.Contains(i))
unique.Add(i);
unique.Sort();
numbers = unique.ToArray();
Используйте реализацию Set.
HashSet , TreeSet или LinkedHashSet , если это Java.
Это можно сделать за амортизированное O (n), используя набор на основе хеш-таблицы.
Псевдокод:
s := new HashSet
c := 0
for each el in a
Add el to s.
If el was not already in s, move (copy) el c positions left.
If it was in s, increment c.
Я согласен с Клетусом. Используйте QuickSort, затем удалите дубликаты
Считать числа ключами.
for each elem in array:
if hash(elem) == 1 //duplicate
ignore it
next
else
hash(elem) = 1
add this to resulting array
end
array flag[N] //N is the max number in the array
for each elem in input array:
if flag[elem - 1] == 0
flag[elem - 1] = 1
add it to resulatant array
else
discard it //duplicate
end