在 Java 中将两个 arrayList 合并为一个新的 arrayList，没有重复并按顺序排列 [英] Merging two arrayLists into a new arrayList, with no duplicates and in order, in Java

问题描述

我正在尝试组合"两个 arrayList，生成一个新的 arrayList，其中包含两个组合的 arrayList 中的所有数字，但没有任何重复的元素，它们应该是有序的.我想出了下面的代码.我完成了它，对我来说很有意义，但我不确定我是否可以使用 <或 > 比较 arrayLists 中的 get(i).我将 array1 中的所有元素添加到 plusArray 中.然后我将检查 plusArray 并将其与 array2 进行比较，以查看 plusArray 中是否存在任何 array2 元素.如果他们这样做，我什么都不做，但如果他们不这样做，那么我会尝试将其添加到正确的位置.也许我的嵌套 for 循环使用不正确?注意:ArrayList 由用户按升序预先排序.

I am trying to "combine" two arrayLists, producing a new arrayList that contains all the numbers in the two combined arrayLists, but without any duplicate elements and they should be in order. I came up with this code below. I run through it and it makes sense to me, but Im not sure if I can be using < or > to compare get(i)'s in arrayLists. I am adding all the elements in array1 into the plusArray. Then I am going through the plusArray and comparing it to array2 to see if any of array2's elements exist inside plusArray. If they do I am doing nothing, but if they dont then I am trying to add it in its correct position. Perhaps my nested for loops being used incorrectly? Note: The ArrayLists are presorted by the user in increasing order.

     ArrayList<Integer> plusArray = new ArrayList<Integer>();
for(int i = 0; i < array1.size(); i++){
    plusArray.add(array1.get(i));
}

for(int i = 0; i < plusArray.size(); i++){
    for(int j = 0; j < array2.size(); j++){

    if(array2.get(j) < plusArray.get(i)){
        plusArray.add(i,array2.get(j));
    }
    else if(plusArray.get(i).equals(array2.get(j))){
        ;
    }
    else if(array2.get(j) > plusArray.get(i)){
        plusArray.add(i, array2.get(j));
    }

}

更新:我不再收到下面的异常了.相反，程序似乎永远运行.我改变了在 < 中添加元素的位置.和 > 条件.///这是我的数组列表时出现的异常:内部集 1: { 1 2 }整数集 2:{ 1 3 4 }

UPDATE: I dont get the exception below anymore. Instead it seems the program runs forever. I changed the location of where to add the elements in the < and > conditions. /// Here is the exception that I get when my array lists are: IntSet 1: { 1 2 } IntSet 2: { 1 3 4 }

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Unknown Source)
at java.util.Arrays.copyOf(Unknown Source)
at java.util.ArrayList.grow(Unknown Source)
at java.util.ArrayList.ensureCapacityInternal(Unknown Source)
at java.util.ArrayList.add(Unknown Source)
at IntSet.plus(IntSet.java:92)
at IntSetDriver.main(IntSetDriver.java:61)

推荐答案

代替你写的代码，你可以使用 ArrayList.addAll() 来合并列表，Collections.sort() 对其进行排序，最后遍历生成的 ArrayList 以删除重复项.因此，聚合复杂度为 O(n)+O(n*log(n))+O(n)，相当于 O(n*log(n))>.

Instead of the code you wrote, you may use ArrayList.addAll() to merge the lists, Collections.sort() to sort it and finally traverse of the resulting ArrayList to remove duplicates. The aggregate complexity is thus O(n)+O(n*log(n))+O(n) which is equivalent to O(n*log(n)).

这篇关于在 Java 中将两个 arrayList 合并为一个新的 arrayList，没有重复并按顺序排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！