Java ArrayList 的合并函数复杂度

Question

我必须编写一个函数来合并两个给定的已排序（从最小到最大）的 ArrayList 或 Integer。合并必须在第一个 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 函数按索引将数据插入指定位置并移动其他元素。 add ArrayList 中的函数 class 使用 System.arraycopy 移动元素，System.arraycopy 使用 O(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);
     }
}

Java ArrayList 的合并函数复杂度

Java ArrayList's merge function complexity

java

algorithm

big-o