ok ! i got a O(n lgn) finally i don know exact complexity Let N = size of first array Find the first N smallest elements using one pointer in each array now swap the list of elements from index 0 to second-pointer in second array to first array with first_poiner+1 to N in first Array I think this is O(n)
On Thu, Jul 7, 2011 at 12:53 PM, Piyush Sinha <[email protected]> wrote: > @radha...i have an algo but its complexity is O(n^2)...check the > following and see if there is any bug as I havent tested for all > cases...also suggestions are welcomed....:) > > main() > { > int a[]= {1,3,77,78,88}; > int b[]= {2,5,79,80,81,99}; > int i=sizeof(a)/sizeof(a[0]) - 1; > int j=sizeof(b)/sizeof(b[0]) - 1; > int temp,k,m; > while(j>=0) > { > if(a[i]>b[j]) > { > temp = a[i]; > k=m=i; > while(b[j]<a[k-1]) k--; > while(i-k) > { > a[i] = a[i-1]; > i--; > } > a[i] = b[j]; > b[j] = temp; > i = m; > } > j--; > } > for(k=0;k<sizeof(a)/sizeof(a[0]);k++) > printf("%d ",a[k]); > puts("\n"); > for(k=0;k<sizeof(b)/sizeof(b[0]);k++) > printf("%d ",b[k]); > puts("\n"); > system("pause"); > } > > > On 7/8/11, radha krishnan <[email protected]> wrote: >> :Given two sorted arrays a[]={1,3,77,78,90} and b[]={2,5,79,81}. Merge >> these two arrays, no extra spaces are allowed. Output has to be >> a[]={1,2,3,5,77} and b[]={78,79,81,90}. >> >> -- >> 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?hl=en. >> >> > > > -- > *Piyush Sinha* > *IIIT, Allahabad* > *+91-8792136657* > *+91-7483122727* > *https://www.facebook.com/profile.php?id=100000655377926 * > > -- > 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?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 [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?hl=en.
