In this HackerRank Find the Running Median problem we have given an input stream of n integers, and we need to add the integer to a running list of integers. and then we need to find the median of the updated list and then print the updated median on the new line.
Problem solution in Python programming.
from heapq import *
under = []
upper = []
N = int(input())
for _ in range(N):
curNumber = int(input())
if (len(upper) == 0):
upper.append(curNumber)
print(curNumber)
continue
middle = upper[0]
if curNumber >= middle:
heappush(upper,curNumber)
else:
heappush(under, -curNumber)
if len(under) >= len(upper):
heappush(upper, -heappop(under))
if len(upper) >= len(under) + 2:
heappush(under, -heappop(upper))
if (len(upper) + len(under)) % 2 == 1:
print(float(upper[0]))
else:
print((float(upper[0]) + -under[0])/2)
Problem solution in Java Programming.
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
try (Scanner in = new Scanner(System.in)) {
int n = in.nextInt();
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < n; ++i) {
int v = in.nextInt();
if (maxHeap.isEmpty() || (v < maxHeap.peek())) {
maxHeap.offer(v);
} else {
minHeap.offer(v);
}
if (maxHeap.size() > (minHeap.size() + 1)) {
minHeap.offer(maxHeap.poll());
}
if (minHeap.size() > (maxHeap.size() + 1)) {
maxHeap.offer(minHeap.poll());
}
if (maxHeap.size() > minHeap.size()) {
System.out.println(maxHeap.peek());
} else if (minHeap.size() > maxHeap.size()) {
System.out.println(minHeap.peek());
} else {
System.out.println(0.5 * (minHeap.peek() + maxHeap.peek()));
}
}
}
}
}Problem solution in C++ programming.
#include <set>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int N;
multiset<int> r;
multiset<int, greater<int> > l;
int main() {
scanf("%d", &N);
for (int i = 0; i < N; ++i) {
int a; scanf("%d", &a);
if (l.empty()) l.insert(a);
else {
if (a > *l.begin()) r.insert(a);
else l.insert(a);
}
if (l.size() > r.size() + 1) {
r.insert(*l.begin());
l.erase(l.begin());
} else if (r.size() > l.size()) {
l.insert(*r.begin());
r.erase(r.begin());
}
if (l.size() > r.size())
printf("%d.0\n", *l.begin());
else
printf("%d.%c\n", (*l.begin() + *r.begin()) / 2, ((*l.begin() + *r.begin()) & 1) ? '5': '0');
}
return 0;
}Problem solution in C programming.
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct {
int *array;
int count;
int size;
} Heap;
void heap_init(Heap *heap, int size) {
heap->size = size;
heap->array = (int *)malloc(size*sizeof(int));
heap->count = 0;
}
void minheap_push(Heap *heap, int x) {
assert(heap->count < heap->size);
int i = heap->count;
int p = (i-1)/2;
while (i > 0 && x < heap->array[p]) {
heap->array[i] = heap->array[p];
i = p;
p = (i-1)/2;
}
heap->array[i] = x;
heap->count++;
}
void maxheap_push(Heap *heap, int x) {
assert(heap->count < heap->size);
int i = heap->count;
int p = (i-1)/2;
while (i > 0 && x > heap->array[p]) {
heap->array[i] = heap->array[p];
i = p;
p = (i-1)/2;
}
heap->array[i] = x;
heap->count++;
}
int minheap_pop(Heap *heap) {
assert(heap->count > 0);
int result = heap->array[0];
int x = heap->array[--heap->count];
int next, i = 0;
while (1) {
int left = 2*i + 1;
int right = left + 1;
if (left >= heap->count) break;
if (heap->array[left] < x) {
if (right < heap->count && heap->array[right] < heap->array[left]) {
next = right;
} else {
next = left;
}
} else if (right < heap->count && heap->array[right] < x) {
next = right;
} else {
break;
}
heap->array[i] = heap->array[next];
i = next;
}
heap->array[i] = x;
return result;
}
int maxheap_pop(Heap *heap) {
assert(heap->count > 0);
int result = heap->array[0];
int x = heap->array[--heap->count];
int next, i = 0;
while (1) {
int left = 2*i + 1;
int right = left + 1;
if (left >= heap->count) break;
if (heap->array[left] > x) {
if (right < heap->count && heap->array[right] > heap->array[left]) {
next = right;
} else {
next = left;
}
} else if (right < heap->count && heap->array[right] > x) {
next = right;
} else {
break;
}
heap->array[i] = heap->array[next];
i = next;
}
heap->array[i] = x;
return result;
}
int main(void) {
int n, x;
scanf("%d", &n);
int size = n/2 + 2;
Heap minheap, maxheap;
heap_init(&minheap, size);
heap_init(&maxheap, size);
for (int i = 0; i < n; i++) {
scanf("%d", &x);
// Decide which heap x should go on.
if (minheap.count == 0) {
minheap_push(&minheap, x);
} else if (x > minheap.array[0]) {
minheap_push(&minheap, x);
} else {
maxheap_push(&maxheap, x);
}
// Then adjust sizes of heaps until they differ by at most 1.
while (minheap.count - maxheap.count > 1) {
int x = minheap_pop(&minheap);
maxheap_push(&maxheap, x);
}
while (maxheap.count - minheap.count > 1) {
int x = maxheap_pop(&maxheap);
minheap_push(&minheap, x);
}
float median;
if (minheap.count == maxheap.count) {
median = 0.5*(minheap.array[0] + maxheap.array[0]);
} else if (minheap.count > maxheap.count) {
median = minheap.array[0];
} else {
median = maxheap.array[0];
}
printf("%.1f\n", median);
}
return 0;
}Problem solution in JavaScript programming.
function processData(input) {
//Enter your code here
var inputArray = input.split('\n');
var testCase = parseInt(inputArray[0]);
var output=[], median=0;
var minHeap = function(){
this.myHeap = [];
this.getSize = function(){
return this.myHeap.length;
};
this.swap = function(i, j){ // swap;
var temp;
temp = this.myHeap[i];
this.myHeap[i] = this.myHeap[j];
this.myHeap[j] = temp;
};
this.bubble = function(i){
var pi = Math.floor(i/2); // parent's index
if(this.myHeap[i] < this.myHeap[pi]){
this.swap(i, pi);
this.bubble(pi);
}
};
this.bubble_down = function(i){
var ci;
if(i==0){
ci = (this.myHeap[1] > this.myHeap[2]) ? 2: 1; // child index choose small one
}else{
ci = (this.myHeap[i*2] > this.myHeap[i*2 +1]) ? i*2+1: i*2; // child index choose small one
}
if(this.myHeap[ci]<this.myHeap[i]){
this.swap(ci, i);
this.bubble_down(ci)
}
};
this.addHeap = function(n){
this.myHeap.push(n);
this.bubble(this.myHeap.length-1);
};
this.peakMin = function(){
return this.myHeap[0];
}
this.getMin = function(){
this.swap(0, this.myHeap.length-1);
var min= this.myHeap.pop();
this.bubble_down(0);
return min;
}
};
var maxHeap = function(){
this.myHeap = [];
this.getSize = function(){
return this.myHeap.length;
};
this.swap = function(i, j){ // swap;
var temp;
temp = this.myHeap[i];
this.myHeap[i] = this.myHeap[j];
this.myHeap[j] = temp;
};
this.bubble = function(i){
var pi = Math.floor(i/2); // parent's index
if(this.myHeap[i] > this.myHeap[pi]){
this.swap(i, pi);
this.bubble(pi);
}
};
this.bubble_down = function(i){
var ci;
if(i===0){
ci = (this.myHeap[1] < this.myHeap[2]) ? 2:1;
}
else{
ci = (this.myHeap[i*2] < this.myHeap[i*2 +1]) ? i*2+1: i*2; // child index choose big one
}
if(this.myHeap[ci]>this.myHeap[i]){
this.swap(ci, i);
this.bubble_down(ci)
}
};
this.addHeap = function(n){
this.myHeap.push(n);
this.bubble(this.myHeap.length-1);
};
this.peakMax = function(){
return this.myHeap[0];
};
this.getMax = function(){
this.swap(0, this.myHeap.length-1);
var max=this.myHeap.pop();
this.bubble_down(0);
return max;
}
};
var minNode = new minHeap(); // keep it default -
var maxNode = new maxHeap();
var current, smallmax, bigmin;
current = parseInt(inputArray[1]);
maxNode.addHeap(current);
median = current;
output.push(median.toFixed(1));
for(var i=2; i<=testCase;i++) {
current = parseInt(inputArray[i]);
if( current < median ){
//prev = maxNode.getMax();
maxNode.addHeap(current);
if (maxNode.getSize() == minNode.getSize()+1) {
median = maxNode.peakMax();
}else if (maxNode.getSize() > minNode.getSize()+1) {
smallmax = maxNode.getMax();
minNode.addHeap(smallmax);
bigmin = smallmax;
smallmax= maxNode.peakMax();
median = (bigmin + smallmax)/2;
}
}else{
minNode.addHeap(current);
if(maxNode.getSize() == minNode.getSize()) {
median = ( maxNode.peakMax() + minNode.peakMin() ) / 2;
}else if (maxNode.getSize() < minNode.getSize()) {
bigmin= minNode.getMin();
maxNode.addHeap(bigmin);
median = bigmin;
}
}
output.push(median.toFixed(1));
}
console.log(output.join('\n'));
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});
0 Comments