Най-добрият алгоритъм за изтриване на дубликати в масив от низове

Днес в училище учителят ни помоли да приложим алгоритъм за изтриване на дубликати. Не е толкова трудно и всички измислиха следното решение (псевдокод):

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. (Ние сме в гимназията и не сме говорили за big-O, но изглежда е 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? (и ако не, защо?)
  • Има ли по-бърз метод за това?

Благодаря


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) със стандартна реализация, ако можете да ги използвате. в противен случай помислете дали да направите лесно рандомизирано бързо сортиране (кодът е дори в wikipedia)).

След това го сканирайте още веднъж. По време на това сканиране просто елиминирайте последователни идентични елементи.

Ако искате да го направите в O(n), можете също да използвате HashSet с елементи, които вече сте виждали. Просто итерирайте веднъж над вашия масив, за всеки елемент проверете дали е във вашия HashSet.

Ако не е там, добавете го. Ако е там, премахнете го от масива.

Обърнете внимание, че това ще отнеме допълнителна памет и хеширането ще има постоянен фактор, който допринася за вашето време на изпълнение. Въпреки че времевата сложност е по-добра, практическото време на изпълнение ще бъде по-бързо само след като надвишите определен размер на масива

person b.buchhold    schedule 20.05.2011
comment
Бихте ли обяснили по-подробно идеята за хешсет, моля? - 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