We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
defget_median(arr):# Must pass sorted arrayn=len(arr)ifn==1:returnarr[0]ifn%2==0:returnround((arr[n//2]+arr[n//2-1])/2,1)returnround(arr[n//2],1)defget_min_index(arr,x):""" Fetch Min Index """# index = 0n=len(arr)# Optimisation# Base Checksifn==0:return0ifx<=arr[0]:return0ifx>=arr[n-1]:returnnl=0r=n-1whilel<r:mid=(l+r)>>1ifarr[mid]<x:l=mid+1else:r=midreturnldefsorted_insert(arr,x):min_index=get_min_index(arr,x)# Insert elementarr.insert(min_index,x)defrunningMedian(a):# Write your code heresorted_arr=[]running_median=[]foreleina:# O(n) * log n time sorted_insert(sorted_arr,ele)# O(log n) time avg~running_median.append(get_median(sorted_arr))returnrunning_median
Find the Running Median
You are viewing a single comment's thread. Return to all comments →
My python3 O (n * log n) solution. for beginners