使用迭代器合併列表

Question

我需要在java中合併兩個字符串列表，我不太確定最好的方式來完成它。我必須使用迭代器和compareTo（）方法。例如...

實施例：L1：A，B，C，d L2：B，d，F，G的結果：A，B，B，C，d，d，F，G

我可以假設輸入列表已經排序，我不能使用contains（）方法。我有一些初步檢查，但while循環是什麼我堅持。

public static ListADT<String> merge(ListADT<String> L1,ListADT<String> L2) throws BadListException { 
ListADT<String> L3 = new ArrayList<String>; 
if(L1 == null || L2 == null) { 
    throw new BadListException(); 
} 
Iterator<String> itr1 = new L1.iterator(); 
Iterator<String> itr2 = new L2.iterator(); 
if(L1.size() == 0 && L2.size() == 0) { 
    return L3; 
} 
if(L1.size() == 0 && L2.size() != 0) { 
    for(int i = 0; i < L2.size(); i++) { 
     return L3.add(L2.get(i)); 
    } 
} 
if(L2.size() == 0 && L1.size() != 0) { 
    for(int i = 0; i < L1.size(); i++) { 
     return L3.add(L1.get(i)); 
    } 
} 
while(itr1.hasNext() || irt2.hasNext()) { 
    //merge the lists here? 
} 

}

任何幫助，將不勝感激。

Answer 1

不要試圖管理一個空列表的合併與非空單作爲一種特殊情況，只是循環，直到迭代器的至少一個是有效的，做你的工作，直接出現：

public static ListADT<String> merge(ListADT<String> L1,ListADT<String> L2) throws BadListException { 
    ListADT<String> L3 = new ArrayList<String>; 

    Iterator<String> itr1 = new L1.iterator(), itr2 = new L2.iterator(); 

    while (itr1.hasNext() || itr2.hasNext()) { 
    if (!itr1.hasNext()) 
     L3.add(itr2.next()); 
    else if (!itr2.hasNext()) 
     L3.add(itr1.next()); 
    else { 
     String s1 = peek from itr1 
     String s2 = peek from itr2; 

     if (s1.compareTo(s2) < 0) { 
     L3.add(itr1.next()); 
     L3.add(itr2.next()); 
     } 
     else { 
     L3.add(itr2.next()); 
     L3.add(itr1.next()) 
     } 
    } 
    } 
} 

Answer 2

下面是一些僞代碼基本算法：

while(itr1 && itr2) 
{ 
    if(itr1 value < it2 value) 
     add itr1 to list 
     increment itr1 

    else 
     add itr2 to list 
     increment itr2 
} 

check if itr1 or itr2 still have more elements 
while itr1 or itr2 has more elements, add those elements to the list 

我們知道列表進行排序，所以在每一個階段，我們只是抓住從每個列表中的最小元素，並將其添加到合併列表。如果最後一個迭代器耗盡而另一個不是，那麼我們可以簡單地遍歷仍然有元素的迭代器，然後將每個元素依次附加到合併列表中。

正如你所看到的，在Java中使用迭代器做這件事有點讓人費解，因爲next()刪除了這個元素。解決此問題的一種方法是利用兩個Queue，每個迭代器一個，將來自該調用的值存儲到next()。然後，您需要比較每個隊列的頭部，將最小值添加到合併列表中，然後將其從各自的Queue中刪除。

Answer 3

如果您只是使用變量來保存來自每個迭代器的當前值，這是相當直接的。此解決方案假定您的列表不包含null，但添加空處理並不困難，因爲列表已排序。

package com.example; 

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Iterator; 
import java.util.List; 

public class IteratorMerge { 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     List<String> list1 = Arrays.asList(new String[]{"A", "B", "C", "D"}); 
     List<String> list2 = Arrays.asList(new String[]{"B", "D", "F", "G"}); 

     System.out.println(merge(list1, list2)); 
    } 

    public static List<String> merge(List<String> L1,List<String> L2) { 
     List<String> L3 = new ArrayList<String>(); 

     Iterator<String> it1 = L1.iterator(); 
     Iterator<String> it2 = L2.iterator(); 

     String s1 = it1.hasNext() ? it1.next() : null; 
     String s2 = it2.hasNext() ? it2.next() : null; 
     while (s1 != null && s2 != null) { 
      if (s1.compareTo(s2) < 0) { // s1 comes before s2 
       L3.add(s1); 
       s1 = it1.hasNext() ? it1.next() : null; 
      } 
      else { // s1 and s2 are equal, or s2 comes before s1 
       L3.add(s2); 
       s2 = it2.hasNext() ? it2.next() : null; 
      } 
     } 

     // There is still at least one element from one of the lists which has not been added 
     if (s1 != null) { 
      L3.add(s1); 
      while (it1.hasNext()) { 
       L3.add(it1.next()); 
      } 
     } 
     else if (s2 != null) { 
      L3.add(s2); 
      while (it2.hasNext()) { 
       L3.add(it2.next()); 
      } 
     } 

     return L3; 
    } 
} 

Answer 4

正如您發現的那樣，使用迭代器合併是一種痛苦。讓我們明確說明了原因：

• 對於合併的每一步，你要檢查都序列的第一個元素，但你只能通過一個想提前。
• Iterator#next()捆綁這些檢查和預先操作到一個操作中，所以不可能檢查兩個序列的頭部，而不還通過兩個前進。

你需要的是一種方法，在一個Iterator的第一個元素偷看沒有推進它。如果你有這種能力，那麼合併看起來是這樣的：

public <T extends Comparable<T>> List<T> merge(Iterator<T> it1, Iterator<T> it2) { 
    PeekableIterator<T> seq1 = new PeekableIterator<T>(it1); 
    PeekableIterator<T> seq2 = new PeekableIterator<T>(it2); 
    List<T> merged = new ArrayList<T>(); 
    while (seq1.hasNext() && seq2.hasNext()) { 
     if (seq1.peekNext().compareTo(seq2.peekNext()) < 0) { 
      merged.add(seq1.next()); 
     } else { 
      merged.add(seq2.next()); 
     } 
    } 
    while (seq1.hasNext()) { 
     merged.add(seq1.next()); 
    } 
    while (seq2.hasNext()) { 
     merged.add(seq2.next()); 
    } 
    return merged; 
} 

而且事實證明，這是不是太難以創造這個PeekableIterator！你只需要跟蹤你目前是否有一個窺視元素，以及那個元素是什麼。

public class PeekableIterator<T> implements Iterator<T> { 
    private final Iterator<T> backing; 
    private boolean havePeek = false; 
    private T peek; 

    public PeekableIterator(Iterator<T> backing) { 
     this.backing = backing; 
    } 

    @Override 
    public boolean hasNext() { 
     return havePeek || backing.hasNext(); 
    } 

    @Override 
    public T next() { 
     if (havePeek) { 
      havePeek = false; 
      return peek; 
     } else { 
      return backing.next(); 
     } 
    } 

    public T peekNext() { 
     if (!havePeek) { 
      peek = backing.next(); 
      havePeek = true; 
     } 
     return peek; 
    } 

    @Override 
    public void remove() { 
     throw new UnsupportedOperationException(); 
    } 
} 

編輯

我沒注意上面的谷歌的番石榴庫，這是因爲這裏的PeekableIterator或多或少相同的參照PeekingIterator評論。如果你有權訪問第三方庫，這對你自己來說肯定會更可取。

Answer 5

公共類MergeIterator {

public static void main(String[] args) { 
     List<String> s1 = new ArrayList<String>(); 
    s1.add("a"); 
    s1.add("z"); 
    s1.add("b"); 
    s1.add("k"); 
    s1.add("c"); 
    Collections.sort(s1); 
    List<String> s2 = new ArrayList<String>(); 
    s2.add("p"); 
    s2.add("a"); 
    s2.add("d"); 
    s2.add("n"); 
    s2.add("m"); 
    Collections.sort(s2); 
    Iterator<String> it1 = s1.iterator(); 
    // sortIterator(it1); 
    Iterator<String> it2 = s2.iterator(); 
    System.out.println(); 
    combine(it1, it2); 
} 

private static Iterator<String> combine(Iterator<String> it1, 
     Iterator<String> it2) { 
    Iterator<String> it3 = null; 
    List<String> l1 = new ArrayList<>(); 
    String s1 = null, s2 = null; 
    while (it1.hasNext() || it2.hasNext()) { //line 1 

    s1 = (s1 == null ? (it1.hasNext() ? it1.next() : null) : s1); //line 2 
    s2 = (s2 == null ? (it2.hasNext() ? it2.next() : null) : s2); // line 3 
     if (s1 != null && s1.compareTo(s2) < 0) { // line 4 
      l1.add(s1); 
      s1 = null; 
     } else { 
      l1.add(s2); 
      s2 = null; 
     } 

    } 
    it3 = l1.iterator(); 
    return it3; 
} 

}