aamir wrote:
> Two sets {ao,a1,a2,..an} and {b0,b1,b2,...bn} having integers in
> increasing order (Sorted arrays of size n).
>
> We have to select n largest numbers from the set {ai+bj} ( This set is
> the sum of two numbers one taken from set A and one taken from set B.It
> is obvious that this set is n^2 in size).Our task is to get n largest
> numbers in O(n.log(n)).
> It can also be solved in O(n).So second step of this problem is to
> develop algo in O(n).
>
> PLEASE DONT WRITE COMPLETE CODE JUST BRIEFLY EXPLAIN THE ALGO.Coz it is
> easier for everybody to understand.Thanks
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
-~----------~----~----~----~------~----~------~--~---
