On 8/1/06, sathiya narayanan <[EMAIL PROTECTED]> wrote:
>
> Given: 2 Arrays of N and M numbers in size.
> We have to find how many common numbers are available ?
>
> Eg: A={8,5,4,2,9}
> B={1,2,3,4,6)
>
> Solution is:2
> Common elements are {2,4}
>
> What i wll do is Sort the array A and then do the binary search for each
> element in array B.So the complexity wll be 0(nlgn)
Actually, you do not need to do binary search after sorting.
Sort arrays and just keep two pointers i and j.
Initially, i=0, j=0
while(i<n && j<m) {
if( a[i] == b[j] ) {
common++;
i++; j++;
}
if( a[i] < b[j] )
i++;
else
j++;
}
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
