# Intersection of two unsorted arrays

Note that: this is not the longest common intersection

-1- The brute-force method takes O(m*n) time (an O(m) linear search n times).
use the brute-force approach - for each element in one array, check if the element exists in the second array by looping thru it

-2- second method takes O(m log m) to sort, plus O(n log m) to search.
construct a binary search tree using the first array and do a look up with the elements in the second array


-3- sort both arrays, then step through them both simultaneously
O(m log m + n log n) for the sorts, and O(m + n) to step through afterwards.

1. // start with arrays a and b.  
2. sort(a);  // log(a.length) time  
3. sort(b);  // log(b.length) time  
4. int aindex = 0;  
5. int bindex = 0;  
6. while (aindex < a.length && bindex < b.length) {  
7.   if (a[aindex] == b[bindex]) {  
8.     print(a[aindex] + " is in both a and b.");  
9.     aindex++;  
10.     bindex++;  
11.   }  
12.   else if (a[index] < b[bindex]) {  
13.     aindex++;  
14.   }  
15.   else {  
16.     bindex++;  
17.   }  
18. }
    

-4- using a hashtable of some sort (e.g. HashSet), such that the whole process is O(m) to store the first array, and O(n) to check the contents of the second.

1. import java.util.HashSet;  
2. import java.util.Set;  
3.   
4.   
5.   
6. public class IntIntersection {  
7.     public static void main(String[] args) {  
8.         int[] firstInts = new int[]{2,3,4,5,5,7,9,0,0,0};  
9.         int[] secondInts = new int[]{2,44,2,33,8,5,12,14,0};  
10.         Set<Integer> intersects = intersectArrays(firstInts, secondInts);  
11.   
12.         // print out the set of intersecting intergers  
13.         for (Integer theInt : intersects) {  
14.             System.out.println("intersect on " + theInt);  
15.         }  
16.   
17.     }  
18.   
19.   
20.     public static Set<Integer> intersectArrays(int[] first, int[] second) {  
21.         // initialize a return set for intersections  
22.         Set<Integer> intsIntersect = new HashSet<Integer>();  
23.   
24.         // load first array to a hash  
25.         HashSet<Integer> array1ToHash = new HashSet<Integer>();  
26.         for (int i = 0; i < first.length; i++) {  
27.             array1ToHash.add(first[i]);  
28.         }  
29.   
30.   
31.         // check second array for matches within the hash  
32.         for (int i = 0; i < second.length; i++) {  
33.             if (array1ToHash.contains(second[i])) {  
34.                 // add to the intersect array  
35.                 intsIntersect.add(second[i]);  
36.             }  
37.         }  
38.   
39.         return intsIntersect;  
40.           
41.     }  
42.   
43. }

If use python, 

we can first set(list1), and set(list2)

find whether there is intersection with two sets:

use the following two functions, or just go through the smaller set and check whether its element also in set2

return [e for e in set1 if e in set2]

if the new list is not empty. 

isdisjoint(other)¶

Return True if the set has no elements in common with other. Sets are disjoint if and only if their intersection is the empty set.

intersection(other, ...)¶

set & other & ...

Return a new set with elements common to the set and all others.

----- get the array lenghth ----

   int arr[] = { 1, 2, 3, 4, 5, 6 };
   int size = sizeof( arr ) / sizeof( arr[0] );
   cout << size << endl;

---- get the str length ----

   char text[100] = "";
   strcpy( text, "John" );
   int len = (int) strlen( text );
   cout << len << endl;

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥

http://www.coderanch.com/t/35439/Programming/Intersection-two-arrays