Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import random
- def select_nth(n, items):
- pivot = random.choice(items)
- lesser = [item for item in items if item < pivot]
- if len(lesser) > n:
- return select_nth(n, lesser)
- n -= len(lesser)
- numequal = items.count(pivot)
- if numequal > n:
- return pivot
- n -= numequal
- greater = [item for item in items if item > pivot]
- return select_nth(n, greater)
- def median(items):
- if len(items) % 2:
- return select_nth(len(items)//2, items)
- else:
- left = select_nth((len(items)-1) // 2, items)
- right = select_nth((len(items)+1) // 2, items)
- return (left + right) / 2
- print (median([7,1,5,4,6,3,2]))
- print (median([1,4,2,3,6,5]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement