Merging two arrayLists into a new arrayList with no duplicates and in order in Java

Question

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  lt  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 lt Integer gt  plusArray   new ArrayList lt Integer gt     for int i   0  i  lt  array1 size    i         plusArray add array1 get i       for int i   0  i  lt  plusArray size    i         for int j   0  j  lt  array2 size    j          if array2 get j   lt  plusArray get i            plusArray add i array2 get j              else if plusArray get i  equals array2 get j                         else if array2 get j   gt  plusArray get i            plusArray add i  array2 get j               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  lt  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

User · Answer

Perhaps my nested for loops being used incorrectly?

Hint: nested loops won't work for this problem. A simple for loop won't work either.

You need to visualize the problem.

Write two ordered lists on a piece of paper, and using two fingers to point the elements of the respective lists, step through them as you do the merge in your head. Then translate your mental decision process into an algorithm and then code.

The optimal solution makes a single pass through the two lists.

User · Answer

Add elements in first arraylist  ArrayList lt String gt  firstArrayList   new ArrayList lt String gt      firstArrayList add  A    firstArrayList add  B    firstArrayList add  C    firstArrayList add  D    firstArrayList add  E      Add elements in second arraylist  ArrayList lt String gt  secondArrayList   new ArrayList lt String gt      secondArrayList add  B    secondArrayList add  D    secondArrayList add  F    secondArrayList add  G      Add first arraylist s elements in second arraylist  secondArrayList addAll firstArrayList     Assign new combine arraylist and add all elements from both arraylists  ArrayList lt String gt  comboArrayList   new ArrayList lt String gt  firstArrayList   comboArrayList addAll secondArrayList     Assign new Set for remove duplicate entries from arraylist  Set lt String gt  setList   new LinkedHashSet lt String gt  comboArrayList   comboArrayList clear    comboArrayList addAll setList     Sorting arraylist   Collections sort comboArrayList     Output   A  B  C  D  E  F  G

User · Answer

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

User · Answer

I got your point that you don t wanna use the built-in functions for merging or remove duplicates from the ArrayList  Your first code is running forever because the outer for loop condition is  Always True    Since you are adding elements to plusArray  so the size of the plusArray is increasing with every addition and hence  i  is always less than it  As a result the condition never fails and the program runs forever  Tip  Try to first merge the list and then from the merged list remove the duplicate elements

User · Answer

Firstly remove duplicates   arrayList1 removeAll arrayList2     Then merge two arrayList   arrayList1 addAll arrayList2     Lastly  sort your arrayList if you wish   collections sort arrayList1     In case you don t want to make any changes on the existing list  first create their backup lists   arrayList1Backup   new ArrayList arrayList1

User · Answer

List lt String gt  listA   new ArrayList lt String gt          listA add  A        listA add  B     List lt String gt  listB   new ArrayList lt String gt          listB add  B        listB add  C     Set lt String gt  newSet   new HashSet lt String gt  listA        newSet addAll listB   List lt String gt  newList   new ArrayList lt String gt  newSet    System out println  New List    newList     is giving you  New List   A  B  C

User · Answer

Add elements in Final arraylist      This will Help you sure    import java util ArrayList  import java util List   public class NonDuplicateList    public static void main String   args         List lt String gt  l1   new ArrayList lt String gt         l1 add  1   l1 add  2   l1 add  3   l1 add  4   l1 add  5   l1 add  6        List lt String gt  l2   new ArrayList lt String gt         l2 add  1   l2 add  7   l2 add  8   l2 add  9   l2 add  10   l2 add  3        List lt String gt  l3   new ArrayList lt String gt         l3 addAll l1       l3 addAll l2       for  int i   0  i  lt  l3 size    i              for  int j i 1  j  lt  l3 size    j                   if l3 get i     l3 get j                      l3 remove j                                     System out println l3          Output    1  2  3  4  5  6  7  8  9  10

User · Answer

your nested for loop    for int j   0  j  lt  array2 size    i       is infinite as j will always equal to zero  on the other hand  i will be increased at will in this loop  You get OutOfBoundaryException when i is larger than plusArray size

User · Answer

Java 8 Stream API can be used for the purpose   ArrayList lt String gt  list1   new ArrayList lt  gt      list1 add  A    list1 add  B    list1 add  A    list1 add  D    list1 add  G     ArrayList lt String gt  list2   new ArrayList lt  gt      list2 add  B    list2 add  D    list2 add  E    list2 add  G     List lt String gt  noDup   Stream concat list1 stream    list2 stream                          distinct                         collect Collectors toList     noDup forEach System out  println     En passant  it shouldn t be forgetten that distinct   makes use of hashCode

User · Answer

I m not sure why your current code is failing  what is the Exception you get    but I would like to point out this approach performs O N-squared    Consider pre-sorting your input arrays  if they are not defined to be pre-sorted  and merging the sorted arrays   http   www algolist net Algorithms Merge Sorted arrays  Sorting is generally O N logN  and the merge is O m n

User · Answer

Add ArrayList1  ArrayList2 and produce a Single arraylist ArrayList3  Now convert it into   Set Unique set   new HashSet Arraylist3     in the unique set you will get the unique elements   Note  ArrayList allows to duplicate values  Set doesn t allow the values to duplicate  Hope your problem solves

User · Answer

Your second for loop should have j   instead of i

User · Answer

Here is one solution using java 8   Stream of list1  list2       flatMap Collection  stream       distinct           sorted   uncomment if you want sorted list      collect Collectors toList

User · Answer

You don t have to handcode this  The problem definition is precisely the behavior of Apache Commons CollectionUtils collate  It s also overloaded for different sort orders and allowing duplicates

[java] Merging two arrayLists into a new arrayList, with no duplicates and in order, in Java

Examples related to java

Examples related to arraylist