하나의 정렬 된 목록에서 두 개의 큰 목록을 병합 (자바)

Question

오늘 인터뷰를했다, 그들은 내게 준 :

목록 A가 있습니다

f 
google 
gfk 
fat 
... 

목록 B가 있습니다

hgt  
google 
koko 
fat 
ffta 
... 

을

그들은 두 목록을 하나의 정렬 된 목록 C에서 병합하도록 요청했습니다.

내가 말한 내용 :
목록 A를 목록 A에 추가 한 다음 목록 A에서 집합을 만든 다음 집합에서 목록을 만듭니다. 그는 목록이 크다고 말했고,이 방법은 성능에 좋지 않을 것이라고 그는 nlog (n)가 될 것이라고 말했다.

이 문제에 대해 어떻게 생각하십니까?

Answer 1

당신의 방법은 O (3N) 추가 공간 (연결된 목록, 집합 및 결과 목록)이 필요합니다. 이는 주요 비효율입니다.

당신이 선택하는 정렬 알고리즘 (QuickSort는 O (1) 공간이 필요함)으로 ListA와 ListB를 정렬 하겠지만 자바의 기본 정렬 전략은 일반적으로 O (N) 추가 공간이 필요한 MergeSort라고 생각합니다. ListA의 "현재"색인을 ListB의 현재 색인으로 검사하고, ListC에 처음 들어 와야 할 요소를 삽입하고 해당 목록의 "현재"색인 계수를 증가시키는 MergeSort 형 알고리즘. 여전히 NlogN이지만 컬렉션에서 컬렉션으로 변환하는 여러 라운드는 피하십시오. 이 전략은 O (N) 추가 공간 만 사용합니다 (ListC의 경우, 소스 목록을 MergeSort하는 경우 N/2 공간이 필요합니다).

IMO 면접관이 원했던 것을 수행하기위한 알고리즘의 하한값은 O (NlogN)입니다. 가장 좋은 솔루션은 공간을 적게 차지하고 성장 모델 내에서 더 효율적이지만 NtN보다 적은 시간에 두 개의 정렬되지 않은 문자열 목록을 정렬 할 수 없습니다.

편집 : (I 무역에 의한 SeeSharper 해요) 자바 내 장점 아니지만, 코드가 아마 같은 것을 보일 것이다 : 나는이 문자열의 목록입니다 있으리라 믿고있어

Collections.sort(listA); 
Collections.sort(listB); 

ListIterator<String> aIter = listA.listIterator(); 
ListIterator<String> bIter = listB.listIterator(); 
List<String> listC = new List<String>(); 

while(aIter.hasNext() || bIter.hasNext()) 
{ 
    if(!bIter.hasNext()) 
     listC.add(aIter.next()); 
    else if(!aIter.hasNext()) 
     listC.add(bIter.next()); 
    else 
    { 
     //kinda smells from a C# background to mix the List and its Iterator, 
     //but this avoids "backtracking" the Iterators when their value isn't selected. 
     String a = listA[aIter.nextIndex()]; 
     String b = listB[bIter.nextIndex()]; 

     if(a==b) 
     { 
     listC.add(aIter.next()); 
     listC.add(bIter.next()); 
     } 
     else if(a.CompareTo(b) < 0) 
     listC.add(aIter.next()); 
     else 
     listC.add(bIter.next());   
    } 
}