sorry it has to be k=k+1 in "k=k-1 goto AGAIN" as C is descending order.
On Sun, Nov 1, 2009 at 1:48 AM, Arun <[email protected]> wrote: > 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.
