How to Find Common Elements of Two UnSorted Array? Below is a simple Java Code which shows it.
Steps:
- Find 1st small array.
- Iterate through small array and find elements in largest array.
- In case of match, add it to separate new array.
- Display final array.
Approach-1:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
package com.crunchify; import java.util.HashSet; /** * @author Crunchify.com */ public class CrunchifyIntersection { public static void main(String[] args) { Integer[ ] arrayOne = { 1, 4, 5, 2, 7, 3, 9 }; Integer[ ] arrayTwo = { 5, 2, 4, 9, 5 }; Integer[ ] common = CrunchifyIntersection.findCommon( arrayOne, arrayTwo ); System.out.print( "Common Elements Between Two Arrays: " ); for( Integer entry : common ) { System.out.print( entry + " " ); } } public static Integer[ ] findCommon( Integer[ ] arrayOne, Integer[ ] arrayTwo ) { Integer[ ] arrayToHash; Integer[ ] arrayToSearch; if( arrayOne.length < arrayTwo.length ) { arrayToHash = arrayOne; arrayToSearch = arrayTwo; } else { arrayToHash = arrayTwo; arrayToSearch = arrayOne; } HashSet<Integer> intersection = new HashSet<Integer>( ); HashSet<Integer> hashedArray = new HashSet<Integer>( ); for( Integer entry : arrayToHash ) { hashedArray.add( entry ); } for( Integer entry : arrayToSearch ) { if( hashedArray.contains( entry ) ) { intersection.add( entry ); } } return intersection.toArray( new Integer[ 0 ] ); } } |
Output:
|
1 |
Common Elements Between Two Arrays: 2 4 5 9 |
Approach-2
Below approach is suggested by our reader Maksudur rahman as you see it in below comment section. Please find here complete example.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
package crunchify.com.tutorials; import java.util.Arrays; import java.util.LinkedHashSet; import java.util.Set; /** * @author Crunchify.com * */ public class CrunchifyIntersection { public static void main(String[] args) { Integer[] arrayOne = { 1, 4, 5, 2, 7, 3, 9 }; Integer[] arrayTwo = { 5, 2, 4, 9, 5 }; Set<Integer> crunchifySet1 = new LinkedHashSet<Integer>(Arrays.asList(arrayOne)); Set<Integer> crunchifySet2 = new LinkedHashSet<Integer>(Arrays.asList(arrayTwo)); for (Integer crunchify : crunchifySet2) { if (!crunchifySet1.add(crunchify)) { System.out.println("The duplicate element of an Array is " + crunchify); } } } } |
Output:
|
1 2 3 4 |
The duplicate element of an Array is 5 The duplicate element of an Array is 2 The duplicate element of an Array is 4 The duplicate element of an Array is 9 |
what will be the complexity in approach2??
since iterating one hashet and simutaneoulsy trying to add in 2nd set.So it will be
o(n) only
since i read add() in set in o(1)