Лучший алгоритм удаления дубликатов в массиве строк

Сегодня в школе учитель попросил нас реализовать алгоритм удаления дубликатов. Это не так сложно, и все придумали следующее решение (псевдокод):

for i from 1 to n - 1
    for j from i + 1 to n
        if v[i] == v[j] then remove(v, v[j])    // remove(from, what)
    next j
next i

Вычислительная сложность этого алгоритма составляет n(n-1)/2. (Мы учимся в старшей школе, и мы не говорили о большом-О, но, похоже, это O(n^2)). Это решение выглядит уродливым и, конечно же, медленным, поэтому я попытался написать что-нибудь побыстрее:

procedure binarySearch(vector, element, *position)
    // this procedure searches for element in vector, returning
    // true if found, false otherwise. *position will contain the
    // element's place (where it is or where it should be)
end procedure

----

// same type as v
vS = new array[n]

for i from 1 to n - 1
    if binarySearch(vS, v[i], &p) = true then
        remove(v, v[i])
    else
        add(vS, v[i], p)      // adds v[i] in position p of array vS
    end if
next i

Таким образом, vS будет содержать все элементы, которые мы уже передали. Если элемент v[i] есть в этом массиве, то он является дубликатом и удаляется. Вычислительная сложность для бинарного поиска составляет log(n), а для основного цикла (второй фрагмент) — n. Поэтому весь СС n*log(n), если не ошибаюсь.

Затем у меня появилась другая идея об использовании бинарного дерева, но я не могу оторваться от нее.
В основном мои вопросы таковы:

  • Верен ли мой расчет CC? (а если нет, то почему?)
  • Есть ли более быстрый метод для этого?

Спасибо


string duplicates algorithm big-o complexity-theory
person BlackBear    schedule 20.05.2011    source источник
comment
Просто для протокола, это действительно O (n ^ 2).   -  person SolarBear    schedule 20.05.2011
comment
Каков тип vS и что именно делает add?   -  person Robin Green    schedule 20.05.2011
comment
@Robin Green: vS похож на v, и add добавляет указанный элемент в указанную позицию   -  person BlackBear    schedule 20.05.2011
comment
Сложность (не время/пространство, а LOC) быстрой версии зависит от того, разрешено ли вам сортировать массив. Если вам разрешено изменять порядок (например, сортировать), все становится очень просто. Если нет, придется прибегнуть к хитрости: отсортировать индексы и использовать их для поиска дубликатов.   -  person LiKao    schedule 20.05.2011
comment
@likao: умный способ, мне нравится :)   -  person BlackBear    schedule 20.05.2011

Ответы (6)


arrow_upward
14
arrow_downward

Самым простым решением будет простая сортировка массива (занимает O (n log n) со стандартной реализацией, если вы можете их использовать. В противном случае рассмотрите возможность простой рандомизированной быстрой сортировки (код есть даже в Википедии)).

После этого отсканируйте его еще раз. Во время этого сканирования просто удаляйте последовательные одинаковые элементы.

Если вы хотите сделать это за O(n), вы также можете использовать HashSet с элементами, которые вы уже видели. Просто выполните итерацию один раз по вашему массиву, для каждого элемента проверьте, находится ли он в вашем HashSet.

Если его там нет, добавьте его. Если он есть, удалите его из массива.

Обратите внимание, что это потребует дополнительной памяти, а хеширование будет иметь постоянный коэффициент, который влияет на время выполнения. Хотя временная сложность лучше, практическое время выполнения будет только быстрее, если вы превысите определенный размер массива.

person b.buchhold    schedule 20.05.2011
comment
Не могли бы вы более подробно объяснить идею hashset, пожалуйста? - person BlackBear; 20.05.2011
comment
@BlackBear: это та же идея, которую объяснил Gumbo, набор хэшей - это просто имя хеш-таблицы, в которой ключ также является значением. - person Matthieu M.; 20.05.2011
comment
HashSet — это структура данных, которая поддерживает проверку вставки и членства за постоянное время. В вашем случае вы, конечно, не хотите реализовывать такую ​​структуру данных самостоятельно, а вместо этого используете существующую для своих языков программирования. Набор позволит добавлять ключи и проверять, содержатся ли они уже в наборе. Поскольку обе операции поддерживаются в постоянное время, и вы выполняете 1 тест на членство (+ 1 вставка или удаление из вашего массива) для каждого элемента, вы получаете O (n). Обратите внимание, что для этого требуется, чтобы удаление/удаление происходило в постоянное время. - person b.buchhold; 20.05.2011
comment
За исключением того, что операции с HashSet являются средним случаем O (1). В худшем случае это O(n) (если у вас есть хэш-функция meshugganah), поэтому вы можете гарантировать только O(n^2) для всего алгоритма. - person Tripp Kinetics; 14.01.2015

arrow_upward
6
arrow_downward

Часто можно использовать компромисс между пространством и временем и инвестировать больше места, чтобы сократить время.

В этом случае вы можете использовать хеш-таблицу для определения уникальных слов.

person Gumbo    schedule 20.05.2011
comment
+1 Отлично, я тоже думал об этом, но не смог найти хэш-функцию. Не могли бы вы предоставить один, пожалуйста? - person BlackBear; 20.05.2011
comment
@BlackBear: многие языки программирования уже имеют такую ​​структуру данных, которая позволяет сопоставлять ключи со значениями. - person Gumbo; 20.05.2011
comment
@BlackBear: не беспокойтесь о хэш-функции, в большинстве языков она уже встроена для строк. - person Matthieu M.; 20.05.2011

arrow_upward
2
arrow_downward

add равно O(n), поэтому ваш расчет CC неверен. Ваш алгоритм O(n^2).

Более того, как будет реализовано remove? Также похоже, что это будет O(n), поэтому начальный алгоритм будет O(n^3).

person Robin Green    schedule 20.05.2011

arrow_upward
0
arrow_downward

Двоичный поиск будет работать, только если искомый массив отсортирован. Я предполагаю, что здесь это не так, иначе вы бы не перебирали весь массив во внутреннем цикле исходного решения.

person OpenSauce    schedule 20.05.2011
comment
Бинарный поиск применяется к vS, а не к v (который является исходным массивом). Я сортирую его, вставляя элементы на свои места. - person BlackBear; 20.05.2011
comment
@BlackBear: ах да, я прочитал это слишком быстро; ). В этом случае мне кажется правильным, предполагая, что vS может быть инициализирован так, чтобы содержать значения, которых нет в v - person OpenSauce; 20.05.2011

arrow_upward
0
arrow_downward

Если порядок окончательного решения не имеет значения, вы можете разбить массив на более мелкие массивы в зависимости от длины строк, а затем удалить дубликаты из этих массивов. Пример:

// You have 
{"a", "ab", "b", "ab", "a", "c", "cd", "cd"}, 

// you break it into 
{"a", "b", "a", "c"} and {"ab", "ab", "cd", "cd"}, 

// remove duplicates from those arrays using the merge method that others have mentioned, 
// and then combine the arrays back together into 
{"a", "b", "c", "ab", "cd"}
person its_me    schedule 20.07.2017

arrow_upward
0
arrow_downward

Это самый короткий алгоритм, который работал, где arrNames и arrScores — это параллельные массивы, и берется самый высокий балл.

I := 0;
J := 0;
//iCount being the length of the array

for I := 1 to iCount do
for J := I + 1 to iCount do

   if arrNames[I] = arrNames[J] then
   begin

     if arrScores[I] <= arrScores[J] then
     arrScores[I] := arrScores[J];

   arrScores[J] := arrScores[iCount];
   arrNames[J] := arrNames[iCount];

   arrScores[iCount] := 0;
   arrNames[iCount] := '';

   Dec(iCount);
   end;
person Verushan Naidoo    schedule 15.10.2018