Effiziente Gruppierung von Elementen einer Liste

Question

Welche Elemente können Sie am effizientesten mit einer Liste von Elementen gruppieren? Wenn der Eingang {a,c,a,b,c,b,b} ist, könnte ein gültiger Ausgang beispielsweise {a,a,b,b,b,c,c} oder {b,b,b,c,c,a,a} lauten. Wenn der Typ des Schlüssels eine Reihenfolge beobachtet, könnte ein Sortieralgorithmus verwendet werden, der uns eine Komplexität von O(nlogn) geben würde.

Der Schlüssel kann jedoch nur für die Gleichheit, nicht aber für die Reihenfolge vergleichbar sein. Zum Beispiel typeof(dog) != typeof(cat), aber es macht keinen Sinn zu fragen, ob typeof(dog) < typeof(cat).

Natürlich könnte die Reihenfolge erzwungen werden (z. B. obj.GetType().ToString() und lexikalische Reihenfolge), aber da eine strikte Reihenfolge nicht notwendig ist (nur Gruppierung), habe ich mich gefragt, ob es einen effizienteren Weg als Sortieren gibt.

Answer 1

I würde eine unsortierte verknüpften Liste und eine Hash-Karte für das Einfügen Punkte, etwa wie folgt (in Pseudocode) verwendet werden:

function group_sort(unsorted_list) 
    node_map = new hash_map 
    sorted_list = new linked_list 
    foreach node in unsorted_list 
    last_node = node_map.get(type_of(node)) 
    if last_node found 
     sorted_list.insert_after(last_node,node) 
    else 
     sorted_list.append(node) 
     node_map.add(type_of(node),node) 
    delete node_map 
    return sorted_list 

Hashzuordnung lookup und Einsatz ist meistens O (1) und die Hash-Karte Einfügungs ist vielleicht sogar selten, abhängig von Ihren Daten. Verknüpfte Listeneinfügung ist immer O (1). Was macht die Funktion fast O (n), und sicherlich O (nlogn).

Answer 2

Sie können jedes Element einfügen in eine multiset