0

今天面试，他们给了我：

清单 A 有：

f  
google   
gfk  
fat  
...

清单 B 有： 

hgt    
google  
koko  
fat  
ffta  
...

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

我所说：

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

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

4

1 回答 1

5

那么您的方法将需要 O(3N) 额外空间（连接列表、集合和结果列表），这是其主要的低效率。

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

IMO 算法做面试官想要做的事情的下限是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());          
   }
}
于 2012-09-05T19:41:03.267 回答