Finding Common Duplicates in Arrays

I have two integer arrays with no info on range of the elements in the arrays. All i know is the lengths of two arrays m and n. Now there are some duplicates in both the arrays. I开发者_Go百科 want to find the lowest common duplicate from both the arrays. Assume that i have limited memory, how do i solve this?

May be MergeSort Algorithm can help you for solving this problem. MergeSort Algorithm is basically for sorting the elements in a list but its main crux is in its Divide and Conquer Approach. As you have mentioned that the memory is limited, hence Divide and Conquer seems to be a reasonable approach for solving the problem.

one possible method (NB! there are probably more efficient ways for doing this both memory and performance wise).

1. create two map instances A and B for first and second array. key is the integer and value is the integer count in the respective array.
2. count the number of occurrences of each integer in both arrays and store them in maps A and B accordingly
3. remove the (key,value) pairs where value is less than 2 in both A and B
4. take the keysets of both A and B and find the intersection.
5. find the lowest key in the intersection, which is the answer