Hi rainix,
I feel that this solution is not correct.
if a[i] + b[j] < a[i-1]+b[n]
we decrease i;
this means that the previous a[i] is never considered again with any
other elements of B. It should be considered again because the
a[i-1]+b[n] is being decreased continuously.
Please correct me if i am wrong.
> i think this ALGO can resovle the problem
>
> 1) do comparison from a[n]+b[n] because it is the largest number in
> the new set;
> 2) can think those numbers, including a[i]+b[n], a[i]+b[n-1],
> a[i]+b[n-2], ... untill a[i]+b[j]<a[i-1]+b[n] (where 0<i<=n, 0<=j<=n),
> are a part of n largest numbers in the new set;
> 3) if a[i]+b[j]<a[i-1]+b[n] and i > 0, then let i = i-1, and
> recursively do the step 2); else
> 4) if a[i]+b[j]<a[i-1]+b[n] and i = 0 and do not find all n largest
> numbers, then find the remained largest numbers from a[1]+b[n] to
> a[1]+b[1].
>
> psuedo-code:
> find (i)
> {
> if (i = 0)
> {
> for (j=n; j>count; j--)
> print (a[1]+b[j]);
> return;
> }
>
> for (j=n, j<=0; j--)
> {
> if (a[i]+b[j]<a[i-1]+b[n])
> break;
> print (a[i]+b[j]);
> count ++;
> if (count == n)
> return;
> }
>
> find(i--);
>
> return;
> }
>
> time cost: O(n)
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
