My short solution, passes all tests. Steps:
1) Started sorting the input list.
2) Iterated over the input list starting from the last element and decreasing the iterator. In each step of this loop, calculate the median of the sorted list and remove the last element of the non sorted original input list from the sorted list (using binary search to locate the element). 3) Reversed the result list.Code:
public static List<Double> runningMedian(List<Integer> a) {var results = new ArrayList<Double>(); var c = List.copyOf(a); Collections.sort(a); for (int k = a.size(); k > 0; k--) { if (k % 2 == 0) { results.add(((double) a.get(k / 2) + a.get((k / 2) - 1)) / 2.0); } else { results.add((double) a.get(k / 2)); } a.remove(Collections.binarySearch(a, c.get(k - 1))); } Collections.reverse(results); return results; }
Hey this is my solution with Js
function runningMedian(a) { let arr = a.map(el => el).sort((a, b) => a - b) let length = arr.length let isOdd = false let mid = [] let half = length/2 const result = [] if(length % 2 !== 0){ isOdd = true mid = [Math.ceil(half)-1] } else { mid = [(half - 1), half] } while(arr.length && a.length){ let pop = arr.indexOf(a.pop()) if(isOdd){ result.unshift(arr[mid[0]]) mid.unshift(mid[0]-1) arr.splice(pop, 1) isOdd = false } else{ let media = (arr[mid[0]] + arr[mid[1]]) / 2 result.unshift(media) mid.pop() arr.splice(pop, 1) isOdd = true } } return result }
Hey There, Here is my C++ Solution using two heaps that passes all test case successfully*****
void insert_increase(vector<int> &H,int x){ H.push_back(x); int i=H.size()-1; while (i>0) { if(H[i]<H[(i-1)/2]) swap(H[i],H[(i-1)/2]); else break; i=(i-1)/2; } } void insert_decrease(vector<int> &H,int x){ H.push_back(x); int i=H.size()-1; while (i>0) { if(H[i]>H[(i-1)/2]) swap(H[i],H[(i-1)/2]); else break; i=(i-1)/2; } } void update1(vector<int> &H,int x){ H[0]=x; int i=0; int n=H.size()-1; while (2*i+1<=n) { int max=i; if(H[2*i+1]>H[i]) max=2*i+1; if((2*i+2<=n)&(H[2*i+2]>H[max])) max=2*i+2; if(max!=i){ swap(H[i],H[max]); i=max; } else break; } } void update2(vector<int> &H,int x){ H[0]=x; int i=0; int n=H.size()-1; while (2*i+1<=n) { int min=i; if(H[2*i+1]<H[i]) min=2*i+1; if((2*i+2<=n)&(H[2*i+2]<H[min])) min=2*i+2; if(min!=i){ swap(H[i],H[min]); i=min; } else break; } } vector<double> runningMedian(vector<int> a) { vector<int>H1; vector<int>H2; vector<double> v; v.push_back(a[0]); insert_decrease(H1,a[0]); for(int i=1;i<a.size();i++){ if(i%2==0) insert_decrease(H1,a[i]); else insert_increase(H2,a[i]); if(H1[0]>H2[0]) { int temp=H1[0]; update1(H1,H2[0]); update2(H2,temp); } if(i%2==0)v.push_back(double(H1[0])); else v.push_back(double((H1[0]+H2[0])/2.0)); } return v; }
return v;}
Python3 solution, passes all test cases. With explanation!
import heapq # We're going to split the list into "low" and "high" halves. # The high half will be a MIN heap, the low half will be a MAX heap. # We'll pop one into the other as needed to keep them close in size. # Then low[0] & high[0] will always return middle values of the list. # In order to implement a max heap with heapq, we just fill it with # negative numbers. So we'll invert numbers we push into low, and # re-invert numbers we pop out of it. def runningMedian(a): low = [] # Lower half of the input high = [] # Upper half of the input ans = [] # List of median values for i in range(len(a)): # First, sort the list value into the correct half. # We'll prioritize high to minimize negative inversion. if i == 0 or a[i] >= med: heapq.heappush(high, a[i]) else: heapq.heappush(low, a[i] * -1) # Now make sure the halves are equally sized. Since high # is filled first, it can be one element longer than low. # Otherwise they must have equal lengths. if len(high) - len(low) > 1: heapq.heappush(low, heapq.heappop(high) * -1) elif len(low) > len(high): heapq.heappush(high, heapq.heappop(low) * -1) # Rest of the logic is easy. If high is longer than low, # there's an odd number of elements in the list, and the # middle value is the bottom of high. Otherwise, there's # an even number of elements in the list, so the median # is half the sum of each half's 0th element. Since low is # stored negative, we'll just subtract it to find the sum. if len(high) > len(low): med = float(high[0]) else: med = float((high[0] - low[0]) / 2) ans.append(med) return ans
My python3 O (n * log n) solution. for beginners
def get_median(arr): # Must pass sorted array n = len(arr) if n == 1: return arr[0] if n % 2 == 0: return round((arr[n // 2] + arr[n // 2 - 1]) / 2, 1) return round(arr[n // 2], 1) def get_min_index(arr, x): """ Fetch Min Index """ # index = 0 n = len(arr) # Optimisation # Base Checks if n == 0: return 0 if x <= arr[0]: return 0 if x >= arr[n-1]: return n l = 0 r = n - 1 while l < r: mid = (l + r) >> 1 if arr[mid] < x: l = mid + 1 else: r = mid return l def sorted_insert(arr, x): min_index = get_min_index(arr, x) # Insert element arr.insert(min_index, x) def runningMedian(a): # Write your code here sorted_arr = [] running_median = [] for ele in a: # O(n) * log n time sorted_insert(sorted_arr, ele) # O(log n) time avg~ running_median.append(get_median(sorted_arr)) return running_median
Load more conversations
Sort 244 Discussions, By:
Please Login in order to post a comment