4

Java で文字列の 2 つのリストをマージする必要がありますが、それを行う最善の方法がよくわかりません。イテレータと 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?
}

}

どんな助けでも大歓迎です。

4

5 に答える 5

4

変数を使用して各反復子からの現在の値を保持するだけであれば、かなり簡単です。このソリューションは、リストに が含まれていないことを前提としていますnullが、リストがソートされているため、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;
    }
}
于 2013-02-11T03:05:03.693 に答える
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

リストがソートされていることがわかっているので、各段階で、各リストから最小の要素を取得して、マージされたリストに追加するだけです。最後に、イテレータの 1 つが使い果たされ、もう 1 つが使い果たされていない場合は、まだ要素を持っているイテレータを単純に繰り返し、各要素を順番にマージされたリストに追加します。

next()これまで見てきたように、Java でイテレーターを使用してこれを行うと、要素が削除されるため、少し面倒です。これを回避する 1 つの方法はQueue、各 Iterator に 1 つずつ、2 つの を使用して、呼び出しからの値を に格納することnext()です。次に、各キューのヘッドを比較し、マージされたリストに最小値を追加してから、それぞれの から削除する必要がありますQueue。

于 2013-02-11T02:03:06.373 に答える
2

おわかりのように、イテレータを使用してマージするのはちょっと面倒です。理由を明示的に述べましょう。

  • マージの各ステップで、両方のシーケンスの最初の要素を検査する必要がありますが、 1 つだけを進めたいとします。
  • Iterator#next()は、これらの検査操作と進行操作を 1 つの操作にまとめているため、両方を進めずに両方のシーケンスの先頭を検査することはできません。

必要なのは、を進めずに の最初の要素を覗く方法です。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();
    }
}

編集

上記のコメントが Google の Guava ライブラリに言及していることに気付きませんでしたPeekingIterator。これは、こちらと多かれ少なかれ同じPeekableIteratorです。サードパーティのライブラリにアクセスできる場合は、独自のライブラリを作成するよりも確実に望ましいでしょう。

于 2014-12-22T06:18:04.487 に答える
0

空のリストと空でないリストのマージを特別なケースとして管理しようとしないでください。少なくとも 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())
      }
    }
  }
}
于 2013-02-11T02:00:23.943 に答える
0

public class 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;
}

}

于 2016-01-16T09:38:58.717 に答える