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;
}
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.
"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.
"Getting the median of a single sorted list is trivial: it is either the central value if the list has an odd-numbered length, or the mean of the two central values otherwise."
Is stated with no proof its not something I recall from collage
It's been 20+ years but this still sounds familiar. Might just be the "that's sounds right so I'll assume I knew it" bias that makes educated people susceptible to subtle propaganda, though. :)
If you want to define the median in a way that generalizes to other situations, this is actually not the way to go! Here's a more general definition: a median of the numbers {x_1, ... x_n} is a number m that minimizes the sum of the absolute deviations, |x_1 - m| + |x_2 - m| + ... + |x_n - m| . Medians are generally not unique via this definition, but they can then be defined for things like sets of points in the plane, in space, etc. (cf. geometric median); the traditional definition is the average of all of the medians under this more general definition.
My favorite problem involving Two Sorted Integer Lists is "Sort X+Y": Given sorted lists X and Y, each of length N, produce the list of N^2 pair-sums in sorted order. Specifically X+Y is the set {a + b for a in X and b in Y}. It seems like you should be able to solve it without relying on a sorting algorithm, since the input lists are already sorted. However, it's unknown if there is a faster algorithm than simply constructing X+Y directly and running a sorting algorithm.
Produce N sorted lists by adding each element in X to the elements of Y. Then mergesort them. Since the blocks you're starting with are runs than one element, you're guaranteed to save the last few (log2 N) steps of recursion. That's faster, although it only a constant factor.
Couldn’t you construct a list of lists, where each is the output of one entry x + Y, and then just merge those lists like one would merge two sorted lists? (Basically just popping off the smallest head at any given time)
You need to do the construction anyways (after all you need the elements of X+Y and you can’t get them without summing)
You end up with N lists to merge, so to find the smallest head at each given time, you'd take log(N) steps.
Given that you have N^2 elements, it would take a total of N^2 log(N) time, which is equivalent in time complexity to simply sorting a list with N^2 elements.
Hmm… what do you mean by faster? I guess you must mean something more nuanced than big-O. From a big-O perspective, sorting is typically O(n log n), but any algorithm that outputs n^2 values must take at least O(n^2) time, so adding O(n log n) makes no difference.
The size of the output is n^2. So you do need at least that much effort. But it's not O(n lg n) to sort n^2 items, it'd be O(n^2) to just construct the output and then O(n^2 lg n) to sort it. So there is potentially a lg n to shave off there.
If the “lists” are not random access, and you know their lengths, then why not just traverse them in parallel? I find it hard to believe you can do it faster than that, and it’s super simple...
You have two indices, one for each list, updated separately. Iterate through a lost until it’s next element is larger than the current element in the other list. Iterate through it until the same condition. Keep going until your present position is at the halfway point, the you’ve got your median.
They don’t mean parallel like two thread, though you could use two coroutines or a similar mechanism.
Thanks. That makes sense. The "in parallel" certainly threw me off.
Although in the article the author at some point switches from lists to vectors, which changes the whole task, and allows for a more efficient implementation (even if it's an answer to a different question).
If they truly are lists (i.e. not random access) then nothing will give you that. If you have the head elements of the lists and you want the median then you have to traverse (m+n)/2 elements just to get to the median. There is no way around that. If you translate the lists to arrays then that’s an o(n+m) operation in itself.
ah yes, of course, that was a misreading on my part, sorry. the title is somewhat misleading, but if you go have a look at the original problem you see that it provides as inputs random-access arrays, not linked lists. i only changed them to lists in the initial, naïve solution in order to keep things simple at first.
31 comments
[ 2.7 ms ] story [ 76.9 ms ] threadhttp://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.
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.
"Getting the median of a single sorted list is trivial: it is either the central value if the list has an odd-numbered length, or the mean of the two central values otherwise."
Is stated with no proof its not something I recall from collage
> //www.bilder-upload.eu/bild-cfb913-1622910941.png.html
(-:
You need to do the construction anyways (after all you need the elements of X+Y and you can’t get them without summing)
Given that you have N^2 elements, it would take a total of N^2 log(N) time, which is equivalent in time complexity to simply sorting a list with N^2 elements.
They don’t mean parallel like two thread, though you could use two coroutines or a similar mechanism.
Although in the article the author at some point switches from lists to vectors, which changes the whole task, and allows for a more efficient implementation (even if it's an answer to a different question).