Java - Optimized way to find duplicates from two ArrayLists/Array

Question

I have two Arrays/ArrayLists of Integer. I want to know the optmized way to find duplicates from two and store into the third one.

Array1 = {1,2,3,6,9,10,15,4};  
Array2 = {4,8,6,5,12,14,1,2,9};  
Result Array= {1,2,3,6,9,10,15,4,8,5,12,14,9}

Regards, Android IT

Is there a limit on the values of the integers in the array (in addition to the 2^31 limit, of course?) — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Jan 22, 2012 at 4:11
Are you sure you need optimization here? How much time your current implementation takes? More than 10ms? — Fedor
– Fedor, Commented Jan 22, 2012 at 4:12
What Fedor said. Also you can't just say "optimized", you need to qualify what you are trying to optimize. Are these lists going to have 10 elements each? 10 million? — MK.
– MK., Commented Jan 22, 2012 at 4:20

Fahim Parkar · Accepted Answer · 2012-01-22 04:31:45Z

2

I would prefer to use Set over HashMap as HashMap need key-value & Sets talks about UNIQUENESS. Sets don't allow duplicates...

answered Jan 22, 2012 at 4:31

Fahim Parkar

31.8k46 gold badges168 silver badges285 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jrom · Accepted Answer · 2012-01-22 04:24:50Z

1

Add elements of both arrays into a HashMap where the value is the number of times the element occurs. Then output it to an array.

answered Jan 22, 2012 at 4:24

Jrom

8611 gold badge10 silver badges20 bronze badges

Comments

Óscar López · Accepted Answer · 2012-01-22 04:42:39Z

1

You mean, a set union?

List<Integer> array1 = Arrays.asList(1,2,3,6,9,10,15,4);
Set<Integer> set1 = new HashSet<Integer>(array1);

List<Integer> array2 = Arrays.asList(4,8,6,5,12,14,1,2,9);
Set<Integer> set2 = new HashSet<Integer>(array2);

set1.addAll(set2);
List<Integer> resultArray = new ArrayList<Integer>(set1);

Now resultArray contains

[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15]

answered Jan 22, 2012 at 4:42

Óscar López

237k38 gold badges321 silver badges391 bronze badges

Comments

Luis · Accepted Answer · 2012-01-22 04:21:07Z

0

The efficient way, sort the arrays (O(n log n)) and iterate through the lowest in both arrays and only select it if is in both (O(n)), otherwise discard.

edited Jan 22, 2012 at 4:21

answered Jan 22, 2012 at 4:14

Luis

1,2947 silver badges9 bronze badges

Collectives™ on Stack Overflow

Java - Optimized way to find duplicates from two ArrayLists/Array

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related