• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Apr 24th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from math import ceil
2.
3.
4. # O(n log n)
5. def simple_median(ls):
6.     n = len(ls)
7.     sort_list = sorted(ls)
8.     return sort_list[n // 2]
9.
10.
11. def median_of_medians(ls, k):
12.     n = len(ls) # O(1)
13.     if k <= 0 or k > n:
14.          raise Exception(f"""parameter k should be greater than 0 and less then the size of the input list.
15.                         Was = {k}.
16.                         Size of list was = {n}.
17.                         """
18.                         )
19.     if n <= 5:
20.         return sorted(ls)[k - 1]
21.
22.     group_medians = [simple_median(ls[i : i + 5]) for i in range(0, n, 5)]
23.
24.     n = ceil(len(group_medians) / 2)
25.
26.     group_mom = median_of_medians(group_medians, n)
27.
28.     left = []
29.     right = []
30.     for x in ls:
31.         if x < group_mom: left.append(x)
32.         elif x > group_mom: right.append(x)
33.
34.
35.     left_len = len(left)
36.     right_len = len(right)
37.     middle_len = len(ls) - right_len - left_len
38.
39.     if left_len <= (k - 1) < (left_len + middle_len) : return group_mom
40.     if k - 1 < left_len   : return median_of_medians(left, k)
41.     if k-1 >= (left_len + middle_len)  : return median_of_medians(right, k - left_len - middle_len)
42.
43. def main():
44.
45.     test_cases = [(9, 9), (10, 9), (11, 9), (12, 11), (13, 11), (14, 11), (15, 15)]
46.     ls = [1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 9, 11, 11, 11, 15, 16, 17, 18, 19, 20, 21]
47.     for case in test_cases:
48.         result = median_of_medians(ls, case)
49.         print("Testing case answer: {}, MoM: {}...".format(case, median_of_medians(ls, case)), end=' ')
50.         assert case == result
51.         print('Ok.')
52.
53.
54. if __name__ == '__main__':
55.     main()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top