size of a=m size of b =n
a[]={1,3,77,78,90} and b[]={2,5,79,81}
lr
while(l<=m && r<=n)
{
if(b[r]wrote:
> @aman: wat u dint get???
>
>
> On Fri, Jul 8, 2011 at 6:34 PM, Aman Goyal wrote:
>
>> i dint get you..
>>
>> one loop to access the first array
@aman: wat u dint get???
On Fri, Jul 8, 2011 at 6:34 PM, Aman Goyal wrote:
> i dint get you..
>
> one loop to access the first array elements and compare with second array,
> and one logn (for) loop to binary search the second array , thts it..
> O(mlogn) is what i am able to understand.
>
> On
i dint get you..
one loop to access the first array elements and compare with second array,
and one logn (for) loop to binary search the second array , thts it..
O(mlogn) is what i am able to understand.
On Fri, Jul 8, 2011 at 5:52 PM, Apoorve Mohan wrote:
> @aman:
>
> Let size of *first array b
@aman:
Let size of *first array be m* and that of the *second array be* *n*.
For m elements in first array you perform binary search therefore time
O(mlogn)
And for those some elements of the first array you perform shifting in array
two...in the worst case for all the elements of first array
yo
Algo:
1 3 77 78 90
2 5 79 81
compare 1 &2 =1
compare 3 &2 =2 and call binary search on 2nd array widot 2 to identify a
proper position for 3 and place it there.
now arrays
1 2 77 78 90
3 5 79 81
3 and 77= swap + binary
compare 3 and 77, swap them
find position of 77 in second array and place th
@dumanshu
> 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 f
@Radha: could u plz elaborate on getting the first n elements???
On Jul 8, 12:55 am, radha krishnan
wrote:
> 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 elemen
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 wrote:
> I remember there is an swap using XOR that uses
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]);
}
