aspose file tools*
The moose likes Beginning Java and the fly likes Find common elements in 3 int array Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Find common elements in 3 int array " Watch "Find common elements in 3 int array " New topic
Author

Find common elements in 3 int array

Raj Kumar Bindal
Ranch Hand

Joined: Apr 15, 2006
Posts: 418
Hi,

i have 3 int arrays. I need to find common elements in those arrays with minimum time/space complexity. Please let me know how can we do this with best performance.

example: if contents of three arrays are {2,4,5,79} {54,6,4,2} {45,4,2,98}, then the output should be {2,4}
John Jai
Bartender

Joined: May 31, 2011
Posts: 1776
Add the array elements into a Map<Integer,Integer> where the key denotes the actual number and the value is a counter. Then on iterating the map checks whether its value is greater than 2 (found in all three arrays).

Utility method to add into a Map. You should call this method will all the three arrays.



You can also use this method to find the counter of numbers in an array for your other question in the thread - http://www.coderanch.com/t/563884/java/java/Finding-top-repeated-numbers-array.
John Jai
Bartender

Joined: May 31, 2011
Posts: 1776
And can you please explain a bit on the below requirement?
Raj Kumar Bindal wrote:with minimum time/space complexity.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19696
    
  20

It can be done a lot easier, using Set and retainAll. Create one set with the contents of the first array, then use retainAll to keep elements that are also in the other arrays.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
John Jai
Bartender

Joined: May 31, 2011
Posts: 1776
hehe Rob... I din't know that.. thanks
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19696
    
  20

You're welcome.

Raj Kumar Bindal, keep in mind that performance is dependent on the selected collections. I suggested Set because then you can use HashSet or LinkedHashSet with constant-time lookup. That way you will need to loop only through one of the Sets when calling retainAll. If you would use List then you would need to loop through both, worsening performance from O(n) (single loop + constant lookup) to O(m*n) (nested loop).
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7814
    
  21

Rob Spoor wrote:It can be done a lot easier, using Set and retainAll. Create one set with the contents of the first array, then use retainAll to keep elements that are also in the other arrays.

Totally agree, but it does depend on Raj's requirements if the arrays can contain duplicate values. If they can't, then Set is definitely the way to go (in fact, the arrays themselves should probably be Sets). If duplicates are allowed, then Raj needs to tell us what what he would expect from something like:
{2,4,5,2,13,2,79} {54,2,6,4,2} {45,2,42,98,2,2}

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19696
    
  20

True. Your example could have two possible outcomes, {2} or {2,2}. I assumed (bad, I know) that the result should be {2}.
 
jQuery in Action, 2nd edition
 
subject: Find common elements in 3 int array