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. Find the Running Median
  2. Discussions

Find the Running Median

Sort by

recency

|

21 Discussions

|

  • gtai_quant
     + 0 comments

    Refined Version by importing bisect

    import bisect

def runningMedian(a):
    medians = []
    arr = []
		
    for i, n in enumerate(a, 1):
        # bisection
        bisect.insort(arr, n)
        
        # median
        m = i // 2
        if i % 2:
            medians.append(round(arr[m], 1))
        else:
            medians.append(round((arr[m] + arr[m-1]) / 2, 1))
						
    
    return medians

  • gtai_quant
     + 0 comments
    def bisect_insort(arr, n):
    i, j = 0, len(arr) - 1
    while i <= j:
        m = (i + j)//2
        if arr[m] > n:
            j = m - 1
        elif arr[m] < n:
            i = m + 1
        else:
            i = m
            break
    arr.insert(i, n)
        
def runningMedian(a):
    medians = []
    arr = []
		
    for i, n in enumerate(a, 1):
        # bisection
        bisect_insort(arr, n)
        
        # median
        m = i // 2
        if i % 2:
            medians.append(round(arr[m], 1))
        else:
            medians.append(round((arr[m] + arr[m-1]) / 2, 1))
            
    return medians

  • vadym_usatiuk
     + 0 comments

    Java O(nlogn)

    public static List<Double> runningMedian(List<Integer> a) {
            List<Double> medians = new ArrayList<>();
            PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder());
            PriorityQueue<Integer> upper = new PriorityQueue<>();

            for (int num : a) {
                if (lower.isEmpty() || num <= lower.peek()) {
                    lower.offer(num);
                } else {
                    upper.offer(num);
                }

                if (lower.size() > upper.size() + 1) {
                    upper.offer(lower.poll());
                } else if (upper.size() > lower.size()) {
                    lower.offer(upper.poll());
                }

                if (lower.size() == upper.size()) {
                    medians.add((lower.peek() + upper.peek()) / 2.0);
                } else {
                    medians.add((double) lower.peek());
                }
            }
            return medians;
        }

  • muxammadnazar_k1
     + 0 comments

    JS

    function runningMedian(a) {
    // Write your code here
    const currentArr = [];
    const results = [];
    
    for(let i = 0; i < a.length; i++) {
        if(!currentArr.length) {
            currentArr.push(a[i]);
        } else if (a[i] < currentArr[0]) {
            currentArr.unshift(a[i]);
        } else if(a[i] > currentArr[currentArr.length - 1]) {
            currentArr.push(a[i])
        } else {
            // seems like we need to insert somewhere in the middle
            let index = 0;
            // Find the correct index to insert the new number
            while (index < a.length && currentArr[index] < a[i]) {
                index++;
            }
            // Insert the new number at the found index
            currentArr.splice(index, 0, a[i]);
        }

        // calculate the median for current list
        if(currentArr.length % 2 === 0) {
            results.push(((currentArr[(currentArr.length/2) - 1] + currentArr[currentArr.length/2]) / 2).toFixed(1));
        } else {
            results.push(currentArr[Math.floor(currentArr.length/2)].toFixed(1));
        }
    }
    
    return results;
}

  • alee235
     + 0 comments

    c++ Using unordered map

    unordered_map<string, int> umap;
vector<int> toReturn;
for(unsigned i = 0; i < queries.size(); ++i) {
    if(queries.at(i).at(0) == "add") {
        for(unsigned j = 0; j < queries.at(i).at(1).size(); ++j){
            ++umap[queries.at(i).at(1).substr(0,j+1)];
        }
    } else if(queries.at(i).at(0) == "find") {
        toReturn.push_back(umap[queries.at(i).at(1)]);
    }
}
return toReturn;