Ищете эффективный способ найти отсортированный заказ из 2 списков

Question

У меня есть 2 набора несортированных целых чисел: установите A и установите B. Но мы не знаем, сколько элементов в SetB заблаговременно.

мне нужно:

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

Что является наиболее эффективным способом сделать это в Java?

Я имею в виду

1. создать ArrayList для множества А и LinkedList для SETB
2. в то время как (множество А и SETB не пусты) рода (множество А) поп множество А удалить целое число от SETB и вставки in setA

Есть ли лучший способ сделать это на Java? Я хотел бы удалить «сортировать в цикле while», если это возможно.

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); 
    } 
} 

Объяснения: класс TreeSet поддерживает набор в виде красно-черного дерева, заказанные на естественной упорядоченности множества элементов; то есть способ Integer.compareTo() в этом случае. Добавление или удаление элемента находит подходящее место в дереве для элемента, а затем добавляет или удаляет его без необходимости сортировки.

isEmpty метод является O (1), а также методы first, add и remove все O (N журнал), где каждый должен быть назван O (N) раз. Создание начальных деревьев также является O (N log N). Таким образом, общая сложность будет O (N log N), где N - общий размер списка.

Answer 2

Вот что я понял из вопроса: нам нужна одна сортированная коллекция, содержащая все элементы как setA, так и setB. Поскольку setA и setB могут содержать одинаковые элементы, мы должны использовать список (сохраняет дубликаты). Если мы не хотим дублировать, просто замените ArrayList на TreeSet и удалите дополнительную сортировку.

Я предполагаю, что оба набора содержат один и тот же тип элементов, а если нет, мы все равно можем использовать Collections.sort, но должны нажимать Comparator на метод sort, который способен сравнивать разные типы объектов.

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

Если вы используете Java 5 и далее, рассмотрим 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(); 
} 

Обратите внимание, что в приведенном выше коде, я первым завернул SETB в связанном списке для поддержки эффективного удаления. Если ваш setB поддерживает эффективное удаление, его не нужно обертывать. Также обратите внимание, что, поскольку вы не заботитесь о перемещении элементов из передней из SETB, ArrayList может поддерживать очень эффективное удаление:

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