@satish
ur solution is of o(nlogn) complexty
@ jitendra
suppose p11 and p21 r pointing at index 0 and p12 at 4 and p22 at 1. now
suppose at ths point d s greater than b and c. now u increment p11 and p21.
but it can be a case that a[0] + b[2] is next greatest value bt t wont
work for ur algo.
On 3 May 2010 00:46, Shishir Mittal <1987.shis...@gmail.com> wrote:
> @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<algogeeks%2bunsubscr...@googlegroups.com>
> .
> 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 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.
