@Algoose : No, it is not necessary that first n elements must contain A[0]
or B[0]. For e.g.
A = {40,30,15,10}
B = {40,30,15,10}
Required 4 largest values = {40+40, 40+30, 40+30, 30+30}.
@Satish:
A very nice algorithm provided by you.
Complexity Analysis for the algorithm provided by you:
Creation of max-heap of n elements = O(n).
Time to add a new element to the heap after extracting the maximum - O(log
n)
Overall Complexity = O(n log n)
Regards,
Shishir
On Sun, May 2, 2010 at 10:52 PM, Satish <satish.mit...@gmail.com> wrote:
> This problem can be simplified to a variation of merge part of merge
> sort algorithm.
>
> - Break the set S having n^2 values into n individual arrays of length
> n, say S1, S2,..Sn, where S1 = [a1+b1, a1+b2,...a1+bn].
> - One can observe that each Si has entries which are themselves sorted
> within Si.
> - Perform merge of S1, S2,..Sn where take the largest values of each
> Si, and create a heap of these individual max values.
> - In each step, return the max value from heap and then add the next
> max value from the Si that had the current max value and add it in the
> max-heap.
> - Repeat this step n times and then exit.
>
> Time: O(n).
>
> Satish
>
> On May 2, 5:41 pm, Algoose Chase <harishp...@gmail.com> wrote:
> > Hi
> >
> > will this work ?
> >
> > since we need Set S with n pairs of largest values , any such pair within
> > the set would (always) contain A[0] or B[0] because they maximize the
> value
> > of the pair.
> >
> > so
> >
> > // code snippet
> > typedef std::vector<int,int> Pairs;
> >
> > Pairs.push(A[0],B[0])
> > int i = 1; // index for ListA
> > int j = 1; // index for list B
> > count = 1;
> > while( count <= n)
> > {
> > if( A[0] + B[j] > B[0] + A[i] )
> > {
> > Pairs.push(A[0],B[j])
> > j++;
> > }
> > else
> > {
> > Pairs.Add(A[i],B[0])
> > i++;
> > }
> > count++;
> >
> > }
> >
> > since there are n items in both the lists, j and i wont go beyond n in
> the
> > while loop
> >
> >
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
