Comment utiliser le tri par fusion pour supprimer les doublons?

Question

J'utilise le tri de fusion récursif pour trier une liste de liens, mais pendant le tri de fusion, je voudrais supprimer les doublons. Quelqu'un a un aperçu de la façon d'accomplir cela?

J'utilise le code C.

Answer 1

Pour utiliser le tri par fusion pour supprimer les doublons, vous devez ignorer les éléments qui sont répétés dans le processus de fusion.

Answer 2

En sorte de fusion vous prenez deux (ou plus) des listes déjà triées appliquer à plusieurs reprises les règles suivantes:

• trouver le moindre/moins des éléments de la partie supérieure de chacune des listes d'entrée, le choix d'une des éléments les plus bas s'il y a un lien
• supprimer cet élément de la liste
• ajouter à votre liste de sortie

pour supprimer les doublons, vous modifiez simplement les règles très légèrement:

• trouver le moindre/moins des éléments de la partie supérieure de chacune des listes d'entrée, en choisissant l'un des éléments les plus bas s'il y a un lien
• supprimer cet élément de la liste
• si elle est le même que le dernier élément que vous avez ajouté à votre liste de sortie, jeter
• autrement, l'ajouter à votre liste de sortie

Cela garantira que deux éléments consécutifs sur votre liste de sortie sont les mêmes, et que les éléments sont en ordre, ce qui h c'est ce que tu cherchais.

Answer 3

Ou tout simplement utiliser tout tri et quand il est terminé, effectuer un balayage sur la liste triée et supprimer des éléments dupliqués (ils seront naturellement à côté de l'autre)

Answer 4

Tenir compte de la fonction de fusion au sein mergesort.

Pendant le processus de fusion, vous comparez bien sûr les éléments les uns avec les autres. Si vous fusionnez 2 listes triées A et B, et si les deux listes contiennent la même valeur x, alors va se comparer les deux éléments identiques. Si vous voulez une preuve, mon approche serait de montrer que s'il y a un cas où deux éléments identiques sont et non comparés, alors une ou les deux listes sont en fait non triées. Preuve par contradiction, bébé!

Ainsi, vous pouvez facilement détecter les cas où deux éléments identiques sont fusionnés dans deux listes. Ensuite, convainquez-vous que s'il y a deux éléments identiques dans deux listes et non en train d'être fusionnés tout à l'heure, ils seront finalement fusionnés et les éléments identiques seront détectés. C'est essentiellement une preuve par induction --- si rien d'autre, clairement la toute dernière fusion (fusionner des listes triées de longueur n/2 et n/2 dans la liste finale de longueur n) va réunir ces éléments.Enfin, convainquez-vous qu'il ne peut exister une liste singulière avec deux éléments du même élément, si vous revenez au cas n = 1 ou n = 0. Ceci est encore inductif car, bien entendu, toute liste plus importante devra d'abord survivre au processus de "filtrage" décrit dans le premier grand paragraphe.

Si vous êtes convaincu de ces trois choses, alors il sera évident que les solutions de Steven ou de Tim sont tout à fait appropriées.

Answer 5

Comme d'autres l'ont souligné, vous aurez besoin de modifier le processus merge pour répondre à vos besoins. Ci-dessous la fonction merge() modifiée pour votre référence (original est here)

function merge(left,right) 
var list result 
while length(left) > 0 and length(right) > 0 
    if first(left) < first(right) // <--- change from <= to < 
     append first(left) to result 
     left = rest(left) 
    else if first(left) > first(right) 
     append first(right) to result 
     right = rest(right) 
    else  // <----- added case to remove duplicated items 
     append first(right) to result 
     left = rest(left) 
     right = rest(right) 
    end 

end while 
if length(left) > 0 
    append left to result 
else 
    append right to result 
return result 

Answer 6

en C++, mais vous pouvez simplement utiliser des tableaux au lieu de vecteurs pour C

#include <iostream> 
#include <vector> 

// merge 2 arrays using a temp array 
void merge (std::vector<int>& v, std::vector<int>& tmpArray, int left, int center, int right) 
{ 
    int leftPos = left; 
    int leftEnd = center; 

    int tmpPos = leftPos; 

    int rightEnd = right; 
    int rightPos = center + 1; 

    // finger matching algo left and right 
    while (leftPos <= leftEnd && rightPos <= rightEnd) 
    { 
    // this first if block here for equals is what does your duplicate removal magic 
    if (v[leftPos] == v[rightPos]) 
    { 
     tmpArray[tmpPos++] = std::move(v[leftPos++]); 
     ++rightPos; 
    } 
    else if (v[leftPos] < v[rightPos]) 
     tmpArray[tmpPos++] = std::move(v[leftPos++]); 
    else 
     tmpArray[tmpPos++] = std::move(v[rightPos++]); 
    } 

    // copy rest of left 
    while (leftPos <= leftEnd) 
    tmpArray[tmpPos++] = std::move(v[leftPos++]); 

    // copy rest of right 
    while (rightPos <= rightEnd) 
    tmpArray[tmpPos++] = std::move(v[rightPos++]); 

    // copy tmp array back to array 
    int numElements = right - left + 1; 
    for (int i = 0; i < numElements; ++i, --rightEnd) 
    v[rightEnd]=std::move(tmpArray[rightEnd]); 
} 

void mergeSort (std::vector<int>& v, std::vector<int>& tmpArray, int left, int right) 
{ 
    if (left < right) 
    { 
    auto center = left + (right - left)/2; 
    mergeSort(v, tmpArray, left, center); 
    mergeSort(v, tmpArray, center+1, right); 
    merge (v, tmpArray, left, center, right); 
    } 
} 

void mergeSort (std::vector<int>& v) 
{ 
    int sz = v.size(); 
    std::vector<int> tmpArray (sz, 0); 
    mergeSort (v, tmpArray, 0, sz-1); 
} 

int main() 
{ 
    std::vector<int> v { 7,8,6,5,4,3,9,12,14,17,21,1,-2,-3,-3,-3,-9,10,11 }; 
    mergeSort (v); 
    for (auto&i : v) 
    std::cout << i << " " ; 
    std::cout << std::endl; 
}