Yep, I was wrong.
for (i = 0; i < m; i++){
if (a[i] > b[0]){
swap(a[i], b[0]);
push b[0] to the end of array-b as far as possible here.
}
}
Then it's not O(m+n) anymore. O(mn) instead.
On Jul 7, 4:33 pm, Yuduo Zhou <[email protected]> wrote:
> I remember there is an swap using XOR that uses no extra space. It's
> also O(1).
> assume we have a O(1) function: swap(a, b)
> a[m], b[n], all sorted separately.
>
> for (i = 0; i < m; i++){
> if (a[i] > b[0]){
> swap(a[i], b[0]);
> if (b[0] > b[1]){
> swap(b[1], b[0]);
> }
> }
>
> }
>
> for(i = 0; i < n; i++){
> if(b[i] > b[i+1]){
> swap(b[i], b[i+1]);
> }
>
> }
>
> This is O(m+n). But I could be wrong.
>
> On Jul 7, 2:54 pm, 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.
