如何合併兩個有序的對象列表？

Question

public class ListMerge 
{ 
    public static void main(String[] args) 
    { 

     Scanner input = new Scanner(System.in); 

     System.out.println ("Input length of arraylist 1:"); 
     int n = input.nextInt(); 
     ArrayList x = new ArrayList(); 
     ArrayList y = new ArrayList(); 
     for (int i = 0; i < n; i++) 
     { 
     System.out.println ("Input x[ " + i +"] :"); 
     x.add(new Integer(i)); 

     } 


     System.out.println ("Input length of arraylist 2:"); 
     int m = input.nextInt(); 


     for (int i = 0; i < m; i++) 
     { 
     System.out.println ("Input y[ " + i +"] :"); 
     y.add(new Integer(i)); 

     } 
     List<Integer> all = new ArrayList<Integer>(); 

     all.addAll(x); 
     all.addAll(y); 
     System.out.println(all); 


    } 
} 

我做了這個 但它沒有從用戶獲取值。 請告訴我爲什麼....

Answer 1

直接從wikipedia：

function merge(left,right) 
    var list result 
    while length(left) > 0 and length(right) > 0 
     if first(left) ≤ first(right) 
      append first(left) to result 
      left = rest(left) 
     else 
      append first(right) to result 
      right = rest(right) 
    end while 
    if length(left) > 0 
     append left to result 
    else 
     append right to result 
    return result 

Answer 2

要完成知識的圓圈，下面是@ unbeli的/維基百科的答案的實現。

public List<T> mergeOrdered(final List<T> list0, final List<T> list1) { 
    List<T> result = new ArrayList<T>(); 

    while (list0.size() > 0 && list1.size() > 0) { 
    if (list0.get(0).compareTo(list1.get(0)) < 0) { 
      result.add(list0.get(0)); 
      list0.remove(0); 
     } 
     else { 
      result.add(list1.get(0)); 
      list1.remove(0); 
     } 
    } 

    if (list0.size() > 0) { 
     result.addAll(list0); 
    } 
    else if (list1.size() > 0) { 
     result.addAll(list1); 
    } 

    return result; 
} 

注意列出使用Arrays.asList()將導致fixed length陣列由哪些元素不能被刪除創建的 - 所以一定要確保你傳遞動態列表！

public List<T> buildDynamicListFromArray(final T[] arr0) { 
    List<T> result = new ArrayList<T>(); 
    int len = arr0.length; 
    for (int i = 0; i < len; i++) { 
     result.add(arr0[i]); 
    } 
    return result; 
} 

Answer 3

這裏使用可能更有效的迭代器，結果ArrayList中，自定義比較器的預ALLOC，和輸入列表上無副作用的實現：

public static <T, C extends Comparator<T>> List<T> mergeOrderedAscending(List<T> list0, List<T> list1, C c) 
{ 
    if(list0 == null || list1 == null || c == null) 
     throw new IllegalArgumentException("null parameter"); 

    Iterator<T> it0 = list0.iterator(); 
    Iterator<T> it1 = list1.iterator(); 

    List<T> result = new ArrayList<T>(list0.size() + list1.size()); 


    T i0 = null; 
    T i1 = null; 


    if(it0.hasNext()) 
     i0 = it0.next(); 
    else 
     i0 = null; 


    if(it1.hasNext()) 
     i1 = it1.next(); 
    else 
     i1 = null; 

    while (i0 != null && i1 != null) { 

     if (c.compare(i0, i1) < 0) { 
      result.add(i0); 

      if(it0.hasNext()) 
       i0 = it0.next(); 
      else 
       i0 = null; 

     } 
     else { 
      result.add(i1); 

      if(it1.hasNext()) 
       i1 = it1.next(); 
      else 
       i1 = null; 
     } 
    } 


    if (i0 != null) { 

     do { 
      result.add(i0); 

      if(it0.hasNext()) 
       i0 = it0.next(); 
      else 
       i0 = null; 
     } while(i0 != null); 
    } 
    else if (i1 != null) { 
     do { 
      result.add(i1); 

      if(it1.hasNext()) 
       i1 = it1.next(); 
      else 
       i1 = null; 
     } while(i1 != null); 
    } 

    return result; 
} 

Answer 4

隨着Google Guava：

Iterable<Integer> all = 
    Iterables.mergeSorted(ImmutableList.of(x, y), Ordering.natural()); 
System.out.println(all);