Recherche d'un moyen efficace de trouver un ordre trié à partir de 2 listes

Question

J'ai 2 ensembles d'entiers non triés: définir A et définir B. Mais nous ne savons pas combien d'éléments sont présents dans setB à l'avance.

Je dois:

while setA and setB are not empty: 
    pop the smallest no from setA 
    move an int from setB to setA 

Quelle est la façon la plus efficace de le faire en Java?

Je pense

1. créer un ArrayList pour Seta et LinkedList pour SetB
2. while (SETA et SetB ne sont pas vides) tri (SETA) pop Seta supprimer un entier de SetB et insert dans setA

Existe-t-il une meilleure façon de faire cela en Java? Je voudrais supprimer le 'tri dans la boucle while' si possible.

Answer 1

TreeSet<Integer> setA = new TreeSet<Integer>(listA); 
TreeSet<Integer> setB = new TreeSet<Integer>(listB); 
while (!setA.isEmpty()) { 
    setA.remove(setA.first()); 
    if (!setB.isEmpty()) { 
     Integer first = setB.first(); 
     setB.remove(first); 
     setA.add(first); 
    } 
} 

Explication: la classe TreeSet maintient l'ensemble dans un arbre rouge-noir qui est commandé sur ordre naturel des éléments de réglage; c'est-à-dire la méthode Integer.compareTo() dans ce cas. L'ajout ou la suppression d'un élément trouve l'emplacement approprié dans l'arborescence de l'élément, puis l'ajoute ou le supprime sans qu'il soit nécessaire de trier.

Le procédé isEmpty est O (1), et les first, addremove et méthodes sont tous O (log N), où chacun doit être appelé O (n) fois. La création des premiers arbres est également O (N log N). Donc, la complexité globale va être O (N log N) où N est la taille totale de la liste.

Answer 2

Voici ce que j'ai compris de la question: Nous avons besoin d'une collection triée qui contient tous les éléments de setA et de setB. Parce que setA et setB peuvent contenir des éléments égaux, nous devrions utiliser une liste (conserve les doublons). Si nous ne voulons pas de doublons, échangez simplement ArrayList par TreeSet et supprimez le tri supplémentaire. Je suppose que les deux ensembles contiennent le même type d'éléments - sinon, nous pouvons toujours utiliser Collections.sort mais nous devons pousser un comparateur à la méthode de tri capable de comparer différents types d'objets.

private Collection<Integer> combineAndSort(Set<Integer>...sets) { 
    Collection<Integer> sorted = new ArrayList<Integer>(); 
// Collection<Integer> sorted = new TreeSet<Integer>(); 
    for(Set<Integer> set:sets) { 
     sorted.addAll(set); 
    } 
    Collections.sort(sorted); // obsolete if using TreeSet 
} 

Answer 3

Si vous utilisez Java 5 partir, pensez java.util.PriorityQueue:

Collection<Integer> setA = ...; 
Collection<Integer> setB = ...; 
if (setA.isEmpty()) { 
    // if A is empty, no need to go on. 
    return; 
} 
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(setA); 
Iterator<Integer> iterB = new LinkedList<Integer>(setB).iterator(); 
// no need to check if A is empty anymore: starting off non-empty, 
// and for each element we remove, we move one over from B. 
while (iterB.hasNext()) { 
    int smallest = pq.poll(); 
    doStuffWithSmallest(smallest); 
    pq.add(iterB.next()); 
    iterB.remove(); 
} 

Notez que dans le code ci-dessus, je suis d'abord Enveloppez la SetB dans une liste, pour soutenir une élimination efficace. Si votre setB prend en charge une suppression efficace, vous n'avez pas besoin de l'envelopper. Notez également que, puisque vous ne se soucient pas des éléments mobiles de la devant SetB, un ArrayList peut prendre en charge l'élimination très efficace:

private <T> T removeOne(ArrayList<T> array) throws IndexOutOfBoundsException { 
    return array.remove(array.size() - 1); 
}