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[0])
  49.         print("Testing case answer: {}, MoM: {}...".format(case[0], median_of_medians(ls, case[1])), end=' ')
  50.         assert case[1] == 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. OK, I Understand
 
Top