以下代码的复杂性

Question

我被赋予了以下任务:

鉴于 - 2列表.第一个列表的大小是N1,第二个列表的大小是N2.每个列表都没有相同的元素.编写一个代码,使用第一个和第二个列表中的元素创建一个新列表.此列表也不应具有相同的元素.还要估算代码的复杂性.

我写了以下代码:

public class Lists {    
    static ArrayList<Integer> getNewList(ArrayList<Integer> list1, 
                                         ArrayList<Integer> list2) {
        ArrayList<Integer> tmp = new ArrayList<>();
        for (Integer i : list1) {
            tmp.add(i);
        }
        for (Integer i : list2) {
            if (!list1.contains(i)) 
                tmp.add(i);
        }
        return tmp;
    }

    public static void main(String[] args) { 
        Integer[] arr1 = {1, 2, 3, 14, 15, 16};        
        Integer[] arr2 = {3, 6, 7, 8, 14};
        ArrayList<Integer> list1 = new ArrayList<>(Arrays.asList(arr1));
        ArrayList<Integer> list2 = new ArrayList<>(Arrays.asList(arr2));
        for (Integer i : getNewList(list1, list2)) {
            System.out.print(i + " ");
        }
    }
}

并说getNewList方法的执行时间与N1*N2成正比.作为回复,我收到以下内容,没有任何解释 - "你错了,这段代码的复杂性不是N1*N2".

那么有人能说出什么是正确的答案吗？并解释如何确定复杂性？

Answer 1

您的代码的复杂性是O(N1*N2),但您可以通过使用a HashSet来确定哪些数字出现在两个列表中,从而做得更好:

static ArrayList<Integer> getNewList(ArrayList<Integer> list1, 
                                     ArrayList<Integer> list2) {
    ArrayList<Integer> tmp = new ArrayList<>();
    HashSet<Integer> dups = new HashSet<>();
    tmp.addAll(list1);
    dups.addAll(list1);
    for (Integer i : list2) {
        if (!dups.contains(i)) 
            tmp.add(i);
    }
    return tmp;
}

这将为您提供O(N1+N2)运行时间,因为插入和查找需要预期的O(1)时间HashSet.