7 ms·
Quickselect and non-randomized variations should get you that; no?
by kopecs 3y ago
Quickselect and non-randomized variations should get you that; no?
- eru 3y agoYes, exactly. But this reduction from 'select n largest' to my problem is still instructive: it tells us that in some sense any (deterministic) solution to my pet problem has to be at least as complicated as (deterministic) median finding.