Hey, it can be done in o(n*logn) time by calling maxheapify function on the
two arrays. Then it decreases the size of the array whose last element is
maximum of the two arrays. I hope you are aware of heap data structure and
you have got the idea how to do it. If not let me know, it will explain it.
Though its not O(n) but still better than o(n^2). I will think of O(n)
solution.....
regards,
Ankit
On Fri, Feb 25, 2011 at 5:36 AM, bittu <shashank7andr...@gmail.com> wrote:
> we have two sorted array a[]={2,6,9,60}; b[]={1,3,5,34,80}; merge the
> array in such way..
> a[]={1,2,3,5}; b[]={6,9,34,60,80}; ..no extra space is allowed..i.e.
> In-Place merging
>
>
> Many of you thinks its easy..but here is q. of minimum complexity i
> have done this but min e complexity high that not seems to be gud..i
> know it can be done O(n) I have tried in O(n^2)...so i looking for
> some gud solution for this
>
> here is my approach lets take two array bigger & smaller
>
> void merge(int[] smaller, int[] bigger)
> {
> int ls=smaller.length;
> int bs=bigger.length;
>
> while(true)
> {
> if(smaller[ls-1]<=bigger[0])
> {
> break;
> }
>
> //swap
> int z=smaller[ls-1];
> smaller[ls-1]=bigger[0];
> bigger[0]=z;
>
> //sort small
> for(int j=ls-2; j>=0;j--)
> {
> if(smaller[j]<smaller[j+1])
> {
> break;
> }
>
> int s=smaller[j+1];
> smaller[j+1]=smaller[j];
> smaller[j]=s;
> }
>
> //sort bigger
> for(int j=0;j<bs-1;j++)
> {
> if(bigger[j]<bigger[j+1])
> {
> break;
> }
>
> int s=bigger[j+1];
> bigger[j+1]=bigger[j];
> bigger[j]=s;
> }
> }
> }
>
>
> Correct me if anything missing or wrong i can improve complexity ???
> Hurray up!!!!!!!
>
>
>
>
> Thanks & Regards
> Shashank >>"The Best Way to Escape From The Problem is ton solve it"
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
