0

私は今日インタビューをしました、そして彼らは私に与えました：

リストAには次のものがあります。

f  
google   
gfk  
fat  
...

リストBには次のものがあります。 

hgt    
google  
koko  
fat  
ffta  
...

彼らは私にこれらの2つのリストを1つのソートされたリストCにマージするように頼みました。

と言いました：

リストBをリストAに追加し、次にリストAからセットを作成し、次にセットからリストを作成しました。インタビュアーは、リストが大きく、この方法はパフォーマンスに良くないだろうと私に言った、彼はそれがnlog（n）になるだろうと言った。

この問題へのより良いアプローチは何でしょうか？

4

1 に答える 1

5

あなたの方法では、O（3N）の追加スペース（連結リスト、セット、および結果リスト）が必要になりますが、これが主な非効率です。

選択した並べ替えアルゴリズムでListAとListBを並べ替えます（QuickSortはO（1）スペースを必要とするインプレースです。Javaのデフォルトの並べ替え戦略は通常O（N）の追加スペースを必要とするMergeSortだと思います）、MergeSortのようなものを使用しますListAの「現在の」インデックスをListBの現在のインデックスに調べ、最初に来る必要のある要素をListCに挿入し、そのリストの「現在の」インデックスカウントをインクリメントするアルゴリズム。それでもNlogNですが、コレクションからコレクションへの複数回の変換は避けてください。この戦略では、O（N）個の追加スペースのみを使用します（ListCの場合、ソースリストをMergeSortする場合はN / 2スペースが必要になります）。

IMOは、インタビュアーが望んでいたことを実行するためのアルゴリズムの下限はO（NlogN）です。最善のソリューションは、追加のスペースが少なく、その成長モデル内でより効率的ですが、ソートされていない2つの文字列リストを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 に答える