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.
Find the Running Median
Find the Running Median
+ 0 comments for c++ , all you need is this :
#include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; typedef tree<int,null_type,less_equal<dbl>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
+ 0 comments this my solution but after the 2 case not working with more data :c help
def runningMedian(a): # Write your code here res = [] temp = [] count = 0 for number in a: temp.append(number) temp = sorted(temp) size = len(temp) middle = round(size / 2) impar = (size % 2) if(impar == 1): currentSize = size -1 middleImpar = round(currentSize / 2) median = temp[middleImpar] res.append(float(median)) else: median = (temp[middle -1] + temp[middle]) / 2 res.append(float(median)) return res
+ 1 comment public static PriorityQueue<int, int> MinHeap = new PriorityQueue<int, int>(); public static PriorityQueue<int, int> MaxHeap = new PriorityQueue<int, int>(new IMaxCompareTo() ); public static List<string> runningMedian(List<int> inputData) { double median = 0; List<string> medians = new List<string>(); for (int i = 0; i < inputData.Count; i++) { int currentValue = inputData[i]; if (MaxHeap.Count == 0 || currentValue <= MaxHeap.Peek()) { MaxHeap.Enqueue(currentValue, currentValue); } else { MinHeap.Enqueue(currentValue, currentValue); } if ((MinHeap.Count - MaxHeap.Count) >= 2) { MaxHeap.Enqueue(MinHeap.Peek(), MinHeap.Peek()); MinHeap.Dequeue(); } else if ((MaxHeap.Count-MinHeap.Count)>=2) { MinHeap.Enqueue(MaxHeap.Peek(), MaxHeap.Peek()); MaxHeap.Dequeue(); } if (MinHeap.Count == MaxHeap.Count) { median = (double)(MinHeap.Peek() + MaxHeap.Peek()) / 2; } else if (MinHeap.Count > MaxHeap.Count) { median = MinHeap.Peek(); } else { median = MaxHeap.Peek(); } var stringM = median.ToString("0.0"); medians.Add(stringM); } return medians; } public class IMaxCompareTo: IComparer<int> { public int Compare(int x, int y) => y.CompareTo(x); }
+ 0 comments Python Interview appropriate heap solution addNum: O(log N) findMedian: O(1) Total = O (log N)
from heapq import heappush, heappop class Median: def __init__(self): self.maxHeap, self.minHeap = [], [] def addNum(self, num): heappush(self.maxHeap, -num) if self.minHeap and self.maxHeap and -self.maxHeap[0] > self.minHeap[0]: heappush(self.minHeap, -heappop(self.maxHeap)) if len(self.minHeap) > len(self.maxHeap) + 1: heappush(self.maxHeap, -heappop(self.minHeap)) if len(self.maxHeap) > len(self.minHeap) + 1: heappush(self.minHeap, -heappop(self.maxHeap)) def findMedian(self): if len(self.maxHeap) > len(self.minHeap): return float(-self.maxHeap[0]) if len(self.maxHeap) < len(self.minHeap): return float(self.minHeap[0]) else: return (self.minHeap[0] - self.maxHeap[0]) / 2 def runningMedian(a): obj = Median() result = list() for i in a: obj.addNum(i) result.append(obj.findMedian()) return result
+ 0 comments def calculate_median(a): mid1 = a[len(a) // 2] mid2 = a[(len(a) - 1) // 2] return (mid1 + mid2) / 2 def sort_insert(arr, num): if not arr: arr.append(num) return start = 0 end = len(arr) -1 while start < end: mid = (end + start) // 2 if arr[mid] < num: start = mid + 1 elif arr[mid] >= num: end = mid - 1 else: if num < arr[start]: arr.insert(start, num) else: arr.insert(start+1, num) def runningMedian(a): arr = [] result = [] for i in range(len(a)): sort_insert(arr, a[i]) result.append(calculate_median(arr)) return result
Load more conversations
Sort 239 Discussions, By:
Please Login in order to post a comment