[algogeeks] Re: Is there any better solution than 0(nlgn) ?

Thu, 03 Aug 2006 01:24:34 -0700

What order can you sort with? certainly gamma(n * log(n)).

On 8/3/06, Atamyrat Hezretguliyew <[EMAIL PROTECTED]> wrote:

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++;
}




--
-- Mohammad
do you C?!!
double m[] = { 9580842103863.650391, 133470973390.236450, 270};
int main(){m[2]--?m[0]*=4,m[1]*=5,main():printf(m);}

Don't attach in Microsoft (.DOC, .PPT) format
http://www.gnu.org/philosophy/no-word-attachments.html
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---

Reply via email to