Java ArrayList的合并函数复杂度

Question

我必须编写一个函数来合并两个给定的排序(从最小到最大)的 Integer ArrayList。合并必须在第一个 ArraList 中完成(在我们的例子中为列表 a)，并且我们必须保持排序顺序(从小到大)。

 void merge(ArrayList<Integer> a, ArrayList<Integer> b) {
    int currentIndexListA = 0;
    int currentIndexListB = 0;

    while(currentIndexListB < b.size()) {
        if(currentIndexListA == a.size() || a.get(currentIndexListA) > b.get(currentIndexListB)) {
            a.add(currentIndexListA, b.get(currentIndexListB));
            currentIndexListB++;
        }
        currentIndexListA++;
    }
}

所以，我对算法的复杂性有些困惑。任务是制定复杂度为 O(N) 的最大效率算法。我认为它的复杂度是 O(N)，但面试官回答说代码效率低下。正确吗？

Answer 1

您通过索引使用了ArrayList.add函数，该函数在指定位置插入数据并移动其他元素。 ArrayList 类中的 add 函数使用 System.arraycopy 来移动元素，而 System.arraycopy 使用 O( 的 native 实现N) 其中 N 是移位元素的数量。所以你的算法效率不高。

正如@SomeDude所说，更好的方法是使用新的ArrayList，如下所示:

import java.util.ArrayList;

public class Main
{
    static void merge2(ArrayList<Integer> a, ArrayList<Integer> b) {
        
        ArrayList<Integer> c = new ArrayList<Integer>();
        int ixa=0, ixb=0;
        int limita = a.size();
        int limitb = b.size();
        int aElem = 0;
        int bElem = 0;
        
        while(ixa+ixb < limita+limitb ) {
            
            aElem = Integer.MAX_VALUE;
            bElem = Integer.MAX_VALUE;
            
            if(ixa < limita) 
                aElem = a.get(ixa);
            
            if(ixb < limitb)
                bElem = b.get(ixb);
                
            if( aElem <= bElem) {
                c.add(aElem);
                ixa++;
            }else {
                c.add(bElem);
                ixb++;
            }
        }

        
        for(Integer aa:c) {
            System.out.println(aa);
        }
    
    }

     public static void main(String []args){
        ArrayList<Integer> a = new ArrayList<Integer>(Arrays.asList(1,3,5));
        ArrayList<Integer> b = new ArrayList<Integer>(Arrays.asList(2,4,6));
        
        merge2(a,b);
        
        ArrayList<Integer> c = new ArrayList<Integer>(Arrays.asList(1,2,3));
        ArrayList<Integer> d = new ArrayList<Integer>(Arrays.asList(5,6,7));

        merge2(c,d);
     }
}