Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
O(n) select solution in Speedy category for Median by nickie
# Find the k'th-smallest value in a, worst case O(n)
# Skip the first d elements and consider only the next n
def select(a, d, n, k):
if n <= 5:
return sorted(a[d:d+n])[k]
# Find median of medians of 5
medians = [sorted(a[i:i+5])[2] for i in range(d, d+n-4, 5)]
m = len(medians)
median = select(medians, 0, m, m // 2)
# Partition around the median.
# a[d:i] <= median
# a[j+1:d+n] >= median
i, j = d, d+n-1
while i <= j:
while a[i] < median: i += 1
while a[j] > median: j -= 1
if i <= j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
if d+k < i: return select(a, d, i-d, k)
else: return select(a, i, n+d-i, k+d-i)
def checkio(data):
n = len(data)
if n % 2 == 1:
return select(data, 0, n, n//2)
else:
return 0.5 * (select(data, 0, n, n//2-1) + select(data, 0, n, n//2))
#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
assert checkio([1, 2, 3, 4, 5]) == 3, "Sorted list"
assert checkio([3, 1, 2, 5, 3]) == 3, "Not sorted list"
assert checkio([1, 300, 2, 200, 1]) == 2, "It's not an average"
assert checkio([3, 6, 20, 99, 10, 15]) == 12.5, "Even length"
Nov. 4, 2013
Comments:
