Javaのイテレータを使用したソート済みリストのマージ

Question

私が使用しているメソッドは、ソートされた2つのリストを取り、ソート順に2つの元のリストのすべての要素を含む単一のリストを返します。

たとえば、元のリストが（1,4,5）および（2,3,6）の場合、結果リストは（1,2,3,4,5,6）となります。

紛失しているものがありますか？

public static<E extends Comparable<E>> List<E> mergeSortedLists(List<E> a, List<E> b) { 
    List<E> result = new ArrayList<E>(); 

    PushbackIterator<E> aIter = new PushbackIterator<E>(a.iterator()); 
    PushbackIterator<E> bIter = new PushbackIterator<E>(b.iterator()); 

    while (aIter.hasNext() && bIter.hasNext()) { 
     if (aIter.next().compareTo(bIter.next()) < 0) { 
      result.add(aIter.next()); 
     } 
     if (bIter.next().compareTo(bIter.next()) > 0){ 
      result.add(bIter.next()); 
     } 
    } 
    while (aIter.hasNext()) { 
     result.add(aIter.next()); 
    } 
    while (bIter.hasNext()) { 
     result.add(bIter.next()); 
    } 
    return result; 
} 

Answer 1

：その場合は、コードは次のようになりますPushbackIteratorの使用：

while (aIter.hasNext() && bIter.hasNext()) { 
    E aElem = aIter.next(); 
    E bElem = bIter.next(); 
    if (aElem.compareTo(bElem) <= 0) { 
     result.add(aElem); 
     bIter.pushback(bElem); 
    } else { 
     result.add(bElem); 
     aIter.pushback(aElem); 
    } 
} 

Answer 2

マージを実行するには、次の値を調べる必要がありますので、次に使用する値を確認してください。

最終的に、リストの1つが他の値よりも前に値を使い果たしてしまうので、チェックする必要があります。

リストはnullの値を含むことができないと仮定して、nullをEnd-Of-Dataマーカーとして使用する方法があります。これはソートする必要があるためです。私はあなたがあなたにこのような何かを意図したと仮定するつもりです

public static <E extends Comparable<E>> List<E> mergeSortedLists(List<E> list1, List<E> list2) { 
    List<E> merged = new ArrayList<>(list1.size() + list2.size()); 

    // Get list iterators and fetch first value from each, if available 
    Iterator<E> iter1 = list1.iterator(); 
    Iterator<E> iter2 = list2.iterator(); 
    E value1 = (iter1.hasNext() ? iter1.next() : null); 
    E value2 = (iter2.hasNext() ? iter2.next() : null); 

    // Loop while values remain in either list 
    while (value1 != null || value2 != null) { 

     // Choose list to pull value from 
     if (value2 == null || (value1 != null && value1.compareTo(value2) <= 0)) { 

      // Add list1 value to result and fetch next value, if available 
      merged.add(value1); 
      value1 = (iter1.hasNext() ? iter1.next() : null); 

     } else { 

      // Add list2 value to result and fetch next value, if available 
      merged.add(value2); 
      value2 = (iter2.hasNext() ? iter2.next() : null); 

     } 
    } 

    // Return merged result 
    return merged; 
} 

テスト

System.out.println(mergeSortedLists(Arrays.asList(1, 4, 5), 
            Arrays.asList(2, 3, 6))); 

出力

[1, 2, 3, 4, 5, 6] 

Answer 3

2つの配列をマージするのと同じ方法を、少し微調整したイテレータで使用することもできます。必要に応じて印刷する代わりに要素を追加することができます。

static void printItr(Iterator<String> it1, Iterator<String> it2) { 
    String firstString=null,secondString = null; 
    boolean moveAheadIt1 = true, moveAheadIt2 = true; 

    while(it1.hasNext() && it2.hasNext()){ 
     firstString = moveAheadIt1 ? it1.next() : firstString ; 
     secondString = moveAheadIt2 ? it2.next() : secondString; 

     if(firstString.compareTo(secondString) < 0){ 
      System.out.println(firstString); 
      moveAheadIt2 = false; 
      moveAheadIt1 = true; 
     }else { 
      System.out.println(secondString); 
      moveAheadIt1 = false; 
      moveAheadIt2 = true; 
     } 
    } 

    while(it1.hasNext()){ 
     System.out.println(it1.next()); 
    } 
    while(it2.hasNext()){ 
     System.out.println(it2.next()); 
    } 

}