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

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

8 голосов
/ 20 мая 2011

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

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.Поэтому весь CC равен n*log(n), если я не ошибаюсь.

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

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

Спасибо

Ответы [ 6 ]

13 голосов
/ 20 мая 2011

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

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

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

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

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

6 голосов
/ 20 мая 2011

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

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

2 голосов
/ 20 мая 2011

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

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

0 голосов
/ 15 октября 2018

Это самый короткий алгоритм, который работал, когда 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;
0 голосов
/ 20 июля 2017

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

// 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"}
0 голосов
/ 20 мая 2011

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

...