Tuesday, December 20, 2016

Find redundant elements in multiple arrays.

Given multiple arrays, find the common entry in them.
For example, given three integer arrays,
{1,3,5,7,9}
{3,8,9}
{2,4,5,7,9}

the answer is {9}, because it exists in all three arrays.
The brute-force way is to O(n^3), if the the size of each array is n.
The better way is to use hashtable.
In Pseudo Code,

Initialize hashtable ( key = number, value=count)
Loop thru all arrays
     If the entry is in hashtable, increase the count.
     else
          insert the entry into hashtable
For Loop hashtable
     if count == number of arrays
          add to result array;
return result array;


     
       

No comments:

Post a Comment