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.
  1. Prepare
  2. Data Structures
  3. Heap
  4. Find the Running Median
  5. Discussions

Find the Running Median

Sort by

recency

|

256 Discussions

|

  • CS_2212256_T
     + 0 comments
    import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static class MinComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer i1, Integer i2) {
            if (i1 < i2) {
                return -1;
            } else if (i1 > i2) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    public static class MaxComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer i1, Integer i2) {
            if (i1 > i2) {
                return -1;
            } else if (i1 < i2) {
                return 1;
            } else {
                return 0;
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        Queue<Integer> minHeap = new PriorityQueue<>(n/2+1, new MinComparator());
        Queue<Integer> maxHeap = new PriorityQueue<>(n/2+1, new MaxComparator());

        for (int i = 0; i < n; i++) {
            int num = in.nextInt();

            if (!maxHeap.isEmpty() && num > maxHeap.peek()) {
                minHeap.offer(num);
            } else {
                maxHeap.offer(num);
            }

            if (minHeap.size() > maxHeap.size() + 1) {
                maxHeap.offer(minHeap.poll());
            } else if (maxHeap.size() > minHeap.size() + 1) {
                minHeap.offer(maxHeap.poll());
            }

            double median = 0.0;
            if (minHeap.size() == maxHeap.size()) {
                median = 0.5 * (minHeap.peek() + maxHeap.peek());
            } else {
                median = (minHeap.size() > maxHeap.size()) ? minHeap.peek() : maxHeap.peek();
            }

            System.out.println(String.format("%1.1f", median));
        }
    }

}

  • 2k23_cscys_23101
     + 0 comments

    import math import os import random import re import sys

    def runningMedian(a):

    if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

    a_count = int(input().strip())

a = []

for _ in range(a_count):
    a_item = int(input().strip())
    a.append(a_item)

result = runningMedian(a)

fptr.write('\n'.join(map(str, result)))
fptr.write('\n')

fptr.close()

  • manceraaxel
     + 0 comments
    import heapq

def runningMedian(a):
    maxh = []
    minh = []
    ans = []

    for aa in a:
        if len(maxh) == 0 or aa <= -maxh[0]:
            heapq.heappush(maxh, -aa)
        else:
            heapq.heappush(minh, aa)

        if len(maxh) > len(minh) + 1:
            heapq.heappush(minh, -heapq.heappop(maxh))
        elif len(minh) > len(maxh):
            heapq.heappush(maxh, -heapq.heappop(minh))

        if len(maxh) > len(minh):
            m = -maxh[0]
        else:
            m = (-maxh[0] + minh[0]) / 2
        ans.append(format(m, ".1f"))

    return ans

  • bahlquist
     + 0 comments

    I am surprised that I was able to get away with using a simple list structure (vector in C++). I started off with a simple, slow solution using std::sort, and then when that didn't pass, I made sure to insert each incoming int in the correct location. That was it. Not hard.

  • saisaranyamyla21
     + 0 comments

    Python3

    import heapq import sys

    def runningMedian(a):

    lower_half = []   
upper_half = []   

result = []

for num in a:

    if len(lower_half) == 0 or num <= -lower_half[0]:
        heapq.heappush(lower_half, -num)  
    else:
        heapq.heappush(upper_half, num)


    if len(lower_half) > len(upper_half) + 1:
        moved_item = -heapq.heappop(lower_half)
        heapq.heappush(upper_half, moved_item)
    elif len(upper_half) > len(lower_half):
        moved_item = heapq.heappop(upper_half)
        heapq.heappush(lower_half, -moved_item)

    if len(lower_half) == len(upper_half):
        median = (-lower_half[0] + upper_half[0]) / 2.0
    else:
        median = -lower_half[0] / 1.0  


    result.append(format(median, ".1f"))

return result

    if name == "main": input = sys.stdin.read().strip().split() n = int(input[0]) a = list(map(int, input[1:n+1])) medians = runningMedian(a) for median in medians: print(median)