java - 如何在Java中将两个大列表合并为一个已排序列表？

Question

我今天接受了面试，他们给了我:

列表 A 具有:

f  
google   
gfk  
fat  
...

列表 B 具有:

hgt    
google  
koko  
fat  
ffta  
...

他们要求我将这两个列表合并到一个已排序的列表 C 中。

我说的是:

我将列表 B 添加到列表 A，然后从列表 A 创建一个集合，然后从该集合创建一个列表。面试官告诉我列表很大，这种方法对性能不好，他说它将是一个nlog(n)。

解决这个问题的更好方法是什么？

Answer 1

那么你的方法将需要 O(3N) 的额外空间(连接的 List、Set 和结果 List)，这是它的主要低效之处。

我会使用您选择的任何排序算法对 ListA 和 ListB 进行排序(QuickSort 就地需要 O(1) 空间；我相信 Java 的默认排序策略是 MergeSort，通常需要 O(N) 额外空间)，然后使用类似 MergeSort 的算法，检查 ListA 的“当前”索引到 ListB 的当前索引，将应该首先出现的元素插入 ListC，并增加该列表的“当前”索引计数。仍然是 NlogN，但可以避免从集合到集合的多轮转换；此策略仅使用 O(N) 额外空间(对于 ListC；如果对源列表进行合并排序，则一路上将需要 N/2 空间)。

在我看来，实现面试官想要的结果的算法的下限是O(NlogN)。虽然最好的解决方案会具有更少的额外空间并且在该增长模型中更高效，但您根本无法在少于 NlogN 的时间内对两个未排序的字符串列表进行排序。

编辑: Java 不是我的强项(我是一名 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());          
   }
}