当递归不是一种选择时合并两个排序列表 - Java

Question

我完全懵了。我查阅了一个接一个的例子和解决方案，没有什么是像这样的结构。

目的是将两个链表按从小到大的排序方式组合在一起。

问题是，必须使用由创建的列表类的对象调用的方法来完成此操作，该对象接受列表类的另一个对象的列表。

编辑:我假设由于方法签名的形式，不可能使用递归。如果不是这样，请纠正我。

。

 list2.mergeSort(list1.getList()); // getList() is a method that returns the list of 
                                   // that object   

签名看起来像

 public List<Integer> mergeSort(List<Integer> otherList)

在组合列表1和其他列表2之后，您可以将合并后的结果列表存储在列表1中，并由mergeSort()方法返回。

我应该补充一下，列表可以是数组或整数，ArrayList，或者其他一些列表或数组形式，如果其他形式比我选择的列表形式更好。

可能的解决方案?

 public List<Integer> mergeSort(List<Integer> otherList){
    List<Integer> temp = new LinkedList<Integer>();
    for(int x = 0; x<list.size(); x++){
        if(list.get(x) < otherList.get(x))
            temp.add(list.get(x));
        else
            temp.add(otherList.get(x));
    }
    list = temp;
    return list;
}

Answer 1

简单(推荐用于实际项目)的方法:

public MyList<E> mergeSort(Collection<? extends E> list) {
    this.addAll(list);
    Collections.sort(this);
    return this;
}

更详细的方法:

public MyList<E> mergeSort(Collection<? extends E> list1) {
    //Copy this list in another one and clear it
    List<E> list2 = new ArrayList<E>(this);
    this.clear();
    //Merge values until one list is exhausted
    Iterator<? extends E> it1 = list1.iterator();
    Iterator<? extends E> it2 = list2.iterator();
    if (it1.hasNext() && it2.hasNext()) {
        E value1 = it1.next(), value2 = it2.next();
        do {
            if (value1.compareTo(value2) <= 0) {
                this.add(value1);
                if (it1.hasNext()) {
                    value1 = it1.next();
                } else {
                    this.add(value2);
                    break;
                }
            } else {
                this.add(value2);
                if (it2.hasNext()) {
                    value2 = it2.next();
                } else {
                    this.add(value1);
                    break;
                }
            }
        } while (true);
    }
    //copy remaining values
    while (it1.hasNext()) {
        this.add(it1.next());
    }
    while (it2.hasNext()) {
        this.add(it2.next());
    }
    return this;
}

我的类定义如下:

public class MyList<E extends Comparable<E>>
    extends ArrayList<E> {

Answer 2

我想你想要合并就地完成?如果是这样的话，它与普通的合并两个列表问题并没有什么不同。

由于我不熟悉Java，我将编写伪代码版本的算法(假设list1和list2已经排序):

let Y refer to the first element in list2
for X in list1 (traversed in ascending order):
    while Y < X:
        insert Y before X
        change Y to point to the next element
while Y is still a valid reference:
    append Y to list1
    change Y to point to the next element

这里的算法破坏性地修改list1，将list2的每个元素插入到正确的位置。如果您希望在比较相等的元素时优先选择list2，则将<更改为<=。

Answer 3

List迭代器保持插入顺序，所以它们并不是真正被设计成你想要的，尽管你可以在使用Collections.sort()合并它们后对列表进行排序。

public List<T> mergeSort(List<T> one, List<T> two) {
    List<T> rc = new ArrayList<>(one.size() + two.size());
    rc.addAll(one);
    rc.addAll(two);
    Collections.sort(rc);
    return rc;
}

你可以在这里添加一个Comparator来控制排序。

您最好使用Set集合，因为它们将根据类型自动排序。如果您对此没有意见，可以这样做:

public Set<T> mergeSort(Set<T> one, Set<T> two) {
    Set<T> rc = new TreeSet<>(one);
    rc.addAll(two);
    return rc;
}

同样，您也可以在这里添加Comparator。

不完全是你想要的，而不是扩展ArrayList或TreeSet，你得到一个通用的方法，你可以在任何地方使用。对于你的问题，我将这样使用:

list1 = Utility.mergeSort(list1, list2);

Answer 4

您可以构建一个Iterable，它可以合并其他两个Iterable，只要它们是Comparable。

class MergedList<T extends Comparable<T>> implements Iterable<T> {
    // The two Iterables we are merging.
    private final Iterable<T> a;
    private final Iterable<T> b;
    // Varargs version left to the student.
    public MergedList(Iterable<T> a, Iterable<T> b) {
        this.a = a;
        this.b = b;
    }
    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            // Grab iterators.
            private final Iterator<T> ia = a.iterator();
            private final Iterator<T> ib = b.iterator();
            // Prime both pumps.
            private T na = ia.hasNext() ? ia.next() : null;
            private T nb = ib.hasNext() ? ib.next() : null;
            // Next to deliver.
            private T n = null;
            @Override
            public boolean hasNext() {
                if (n == null) {
                    // Pick one - either null means the other one - otherwise compare.
                    n = na == null ? nb : nb == null ? na : na.compareTo(nb) < 0 ? na : nb;
                    if (n != null) {
                        // Consume one.
                        if (na != null && n == na) {
                            // Get next from a.
                            na = ia.hasNext() ? ia.next() : null;
                        } else if (nb != null && n == nb) {
                            // Get next from b.
                            nb = ib.hasNext() ? ib.next() : null;
                        }
                    }
                }
                return n != null;
            }
            @Override
            public T next() {
                T next = n;
                n = null;
                return next;
            }
        };
    }
}
public void test() {
    List<String> a = Arrays.asList("A", "C", "E");
    List<String> b = Arrays.asList("B", "D", "F");
    for (String s : new MergedList<>(a, b)) {
        System.out.println(s);
    }
}

Answer 5

   public List<Integer> mergeSort(List<Integer> otherList){
        List<Integer> list1 = new ArrayList<>(); // this should be list1
        list1.addAll(otherList);
        /** can also use Collections.sort(list1); */
        Collections.sort(list1,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2); //Change to o2.CompareTo(o1) for descending order
            }
        });
        return list1;
    }