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.
