java - Java ArrayList 的合并函数复杂度

Question

我必须编写一个函数来合并两个给定的排序（从最小到最大）的整数数组列表。合并必须在第一个 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) 复杂度，但面试官回应说代码效率低下。这是对的吗 ？

标签： javaalgorithmbig-o

Answer 1

您使用ArrayList.add函数按索引将数据插入到指定位置并移动其他元素。ArrayList类中的add函数用于移动元素并使用 O(N) 的本机实现，其中 N 是移动元素的数量。所以你的算法效率不高。System.arraycopySystem.arraycopy

@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);
     }
}