liyichao.good
BAN USERThanks, My solution's problem is to assume b[0] > a[m-2]
- liyichao.good March 10, 2013no, I don't, I add an example now, it may be easier to understand.
- liyichao.good March 09, 2013the code explains well. Anyway, I explain more.
if b[(m+n)/2-m] >= a[m-1], then a[0], a[1], ... a[m-1], b[0], b[1], ... b[(m+n)/2-m-1] is smaller than b[(m+n)/2-m], which means it is c[(m+n)/2] in the combined array c.
My answer is wrong. I assume b[0] > a[m-2]. Anyway, keep it.
my solution is O(1).
assume a has m elements, b has n elements.
assume m <= n.
The question is to find the (m+n)/2 in the combined array, (m+n)/2 is bigger than m.The miracle happens when we compare the b[(m+n)/2 - m ] and a[m-1]:
if b[(m+n)/2-m] >= a[m-1]
return b[(m+n)/2 - m];
else
return a[m-1] >= b[(m+n)/2-m+1] ? b[(m+n)/2-m+1] : a[m-1];
for example
a[] = { 1, 2, 5, 9}
b[] = { 8, 13 ,15 ,20, 21}
we want c[4] in combined array c.
compare b[0] = 8 and a[3] = 9
b[0] < a[3]
then compare b[1] and a[3],
b[1] > a[3] then the result c[4] = a[3] = 9.
how about {7,5,2}, in this example, you never go into the second branch.
when a[i] < min, there is possibility that a[i] - min is maximum.
here is my solution.
- liyichao.good March 29, 2013