I think daizi sheng is right, its O(n^2) if i rewrite his algo slgihtly, which makes me more clear A,B -> sorted in ascending C in descending foreach(ai in A) ck = largest element in C j=1 AGAIN: if(ai + bj + ck == 0) algorithm over if(ai + bj + ck > 0) k=k-1 goto AGAIN if(ai + bj + ck < 0) j=j+1
On Sun, Nov 1, 2009 at 1:28 AM, anilkumarmyla <[email protected]>wrote: > That way your solution takes more than O(N^2), because of the AGAIN loop. > > > On Sun, Nov 1, 2009 at 1:09 PM, daizi sheng <[email protected]> wrote: > >> with all arrays sorted firstly, if you enumerate ai, bj in ascedning >> order, >> ck will be sure in descending order. >> >> foreach(ai in A) >> ck = largest element in C >> foreach(bj in B) >> AGAIN: >> if(ai + bj + ck == 0) algorithm over >> if(ai + bj + ck > 0) ck change to its neighbor in C and goto AGAIN >> if(ai + bj + ck < 0) continue checking next bj >> > -- > 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]. > 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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
