3 ms·
Presumably the list is not ordered adversarially, so you can just use quickselect, at O(n) running time.
by School-Cotton 4y ago
Presumably the list is not ordered adversarially, so you can just use quickselect, at O(n) running time.
- pjscott 4y agoMy personnel records are always ordered adversarially, on general principle. :-) But if you’re willing to assume that none of the ages are more than some reasonable constant bound, like no employees over the age of 65535 or something, then there’s a fun guaranteed O(n) algorithm closely related to counting sort.
- tantalor 4y ago> counting sort There's the right answer right there. I'll add: let the AI handle the details. def getMedianAge(person_list): # Let copilot fill in rest
- naniwaduni 4y agoI wouldn't really expect your personnel ages to leave the range of an unsigned octet in the foreseeable future. Hell, I'm pretty sure we're not expecting to have personnel exceeding 127yo anytime soon. (Note, however, that counting occurrences is in principle at least O(log n) space and, without a bit of cleverness, likely O(n log n) time—your integers need to be O(log n) wide to count that big!)
- exact_string 4y agoYou can use the median of medians with quickselect to guarantee the O(N) time complexity.