3 ms·
Fun problem, conceptually easy but very prone to off-by-one errors. I think it's a bit easier to implement median using kth. Also it doesn't need recursion, one
by cousin_it 5y ago
Fun problem, conceptually easy but very prone to off-by-one errors. I think it's a bit easier to implement median using kth. Also it doesn't need recursion, one loop with fixed space usage is enough. Here's my JS code:
function kth2(a,b,k) {
var ai=0,aj=a.length,bi=0,bj=b.length,d=1;
while (true) {
if (ai==aj) return b[bi+d*k];
if (bi==bj) return a[ai+d*k];
var m=d*(aj-ai),n=d*(bj-bi);
if (k<(m+n)/2) [ai,aj,bi,bj,d,k] = [aj-d,ai-d,bj-d,bi-d,-d,m+n-1-k];
var ak=Math.floor((m+1)/2),bk=Math.floor((n+1)/2);
if (d*a[ai+d*ak-d]<d*b[bi+d*bk-d]) [ai,k] = [ai+d*ak,k-ak];
else [bi,k] = [bi+d*bk,k-bk];
}
}
function median2(a,b) {
var n = a.length+b.length;
if (n%2 == 1) return kth2(a,b,(n-1)/2);
else return (kth2(a,b,n/2-1)+kth2(a,b,n/2))/2;
}
- mike_kamau 5y agoCould you please add a description to your solution?
- soegaard 5y agoHere is a Racket (/Scheme) version of the JavaScript solution with a thorough explanation. http://pasterack.org/pastes/80529 http://pasterack.org/pastes/80529 Note that this solution is using a standard imperative style, with a loop over that narrows down the location of the sought of element in two subvectors of a and b.
- cousin_it 5y agoWow! Yes, this is all exactly right.
- prezjordan 5y agoFound the APL programmer
- qsort 5y ago"Fun", "conceptually easy" and "very prone to off-by-one or other trivial errors" is basically a description of 99% of the problems on LeetCode. The last one is particularly annoying because most problems could be easily tweaked with e.g. restrictions on the size of input or test cases to avoid those issues.