Sort both the lists...
(Keep track of their original indices as we need to return to original list)
Modify the merge process of merge_sort:
// Assume size of list1 is m and that of list2 is n
curr_list1=0;curr_list2=0;curr_output=0;
while( curr_list1 < m && curr_list2 < n )
{
If (list1[curr_list1] == list2[curr_list2] )
{
int temp = list1[curr_list1];
output[curr_output++] = temp;
//These while loops to ignore duplicates
while( curr_list1 < m && list1[curr_list1] == temp )
curr_list1++;
while( curr_list2 < n && list2[curr_list2] == temp )
curr_list2++;
}
else if( list1[curr_list1] < list2[curr_list2] )
{
curr_list1++;
}
else
{
curr_list2++;
}
}
//Now output contains intersection of both the lists.
//Revert back to original lists.
TC: O(mlogm) + O(nlogn) + O(min (m,n) ) + O(m) + O(n) = O(mlogm + nlogn)
SC: O(m+n) (To maintain associative array / copy of original lists) +
O(min (m,n)) (To create output list) = O( m+n )
Correct me if I am wrong anywhere in the analysis.
On Wed, Aug 3, 2011 at 4:31 PM, ankit sambyal <[email protected]>wrote:
> Given two lists write a function which returns a list which is the
> intersection of the two lists.the original lists should remain same.
> (Intersection - if first list is say,1,20 3,45 and second list is 3,24
> ,45,90,68 then intersection should be 3,45 )
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
