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 

자바 것을 할 수있는 가장 효율적인 방법은 무엇입니까?

나는

1. 이 SETB을위한 세타와 LinkedList의에 대한 ArrayList를을 만들 생각입니다
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 방법 (1)은 O이고 first, addremove 및 방법은 각각 O (N) 배라고하는 모든 O (N 로그)이다. 초기 트리 집합을 생성하는 것도 O (N log N)입니다. 따라서 전체적인 복잡도는 O (N log N)가 될 것입니다. 여기서 N은 전체 목록 크기입니다.

Answer 2

다음은 질문에서 이해할 수 있습니다. setA와 setB의 모든 요소가 포함 된 정렬 된 컬렉션이 하나 필요합니다. setA와 setB는 같은 항목을 포함 할 수 있으므로 목록을 사용해야합니다 (중복 보관). 중복을 원하지 않는다면 TreeSet에 의해 ArrayList를 교환하고 여분의 정렬을 제거하십시오.

두 세트 모두 동일한 유형의 요소를 포함한다고 가정합니다. 그렇지 않은 경우 Collections.sort를 계속 사용할 수 있지만 Comparator를 다른 유형의 개체를 비교할 수있는 정렬 방법으로 푸시해야합니다.

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

는 이후 자바 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가 효율적인 제거를 지원하면 래핑 할 필요가 없습니다.

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