Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Speedy category for Median by tokyoamado
import random
def checkio(data):
n = len(data)
if n % 2 == 1:
return quickselect(data, n // 2)
else:
return (quickselect(data, n // 2 - 1) + quickselect(data, n // 2)) / 2
def quickselect(data, n):
if data == []:
return None
else:
pivot = random.choice(data)
(partl, cntl), (partr, cntr) = partition(data, pivot)
if n == cntl:
return pivot
elif n < cntl:
return quickselect(partl, n)
else:
return quickselect(partr, n - cntl - 1)
def partition(data, pivot):
partl = []
partr = []
cntl = cntr = 0
for x in data:
if x < pivot:
partl.append(x)
cntl += 1
else:
partr.append(x)
cntr += 1
partr.remove(pivot)
cntr -= 1
return (partl, cntl), (partr, cntr)
Oct. 16, 2017
