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

Thu, 03 Aug 2006 01:22:40 -0700

I think this algorithm's time complexity is O(N ^ 2), isn't it?

On 8/3/06, Nat (Padmanabhan Natarajan) <[EMAIL PROTECTED]> wrote:
If you know the range of numbers say 0 to L and there are no repetitions (this is just for convenience)

take a bitvector B of size L

commonCount := 0
for (i, j) in M, N
  if(i == j) //direct hit
     B[i] = 1
     commonCount++
  else if(B[i] = 1 AND B[j] = 1)
     commonCount += 2
  else if(B[i] = 1) //j has already hit this i value
     commonCount++;
     B[j] = 1;
   else if(B[j] = 1)
     commonCount++;
     B[i] = 1
   else
      B[i] = B[j] = 1

Cheers,
 
Nat

On 8/2/06, Mohammad Moghimi <[EMAIL PROTECTED] > wrote:
If you know the range of numbers, you can allocate an array of that size, and ...
are you satisfied with this?!!!

 
On 8/2/06, sathiya narayanan < [EMAIL PROTECTED] > wrote:
yup thanx, is there any way other than hashing ? which should be better than O(nlgn)




 

, 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




 

, 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