4

我需要在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?
}

}

任何帮助，将不胜感激。

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

我们知道列表是排序的，所以在每个阶段，我们只需从每个列表中抓取最小的元素并将其添加到合并列表中。如果最后一个迭代器用完而另一个没有用完，那么我们可以简单地遍历仍然有元素的那个，依次将每个元素附加到合并列表中。

如您所见，在 Java 中使用迭代器执行此操作有点痛苦，因为next()会删除元素。解决此问题的一种方法是使用两个Queues，每个迭代器一个，用于存储来自对 的调用的值next()。然后，您需要比较每个队列的头部，将最小值添加到合并列表中，然后将其从各自的Queue.

于 2013-02-11T02:03:06.373 回答
2

正如您所发现的，使用迭代器进行合并有点痛苦。让我们明确说明原因：

  • 对于合并的每一步，您都想检查两个序列的第一个元素，但您只想前进一个。
  • 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();
    }
}

编辑

我没有注意到上面提到的PeekingIterator谷歌番石榴库中的评论，它或多或少与PeekableIterator这里的相同。如果您可以访问第三方库，这肯定比滚动您自己的库更可取。

于 2014-12-22T06:18:04.487 回答
0

不要尝试将空列表与非空列表合并为一种特殊情况，只需循环直到至少有一个迭代器有效并直接在那里完成您的工作：

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

公共类 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 回答