In this tutorial, we are going to solve or make a solution to the Median Updates problem. so here we first need to make an empty list and then add or remove the elements from the list and then after each operation, we need to print the median.
Problem solution in Python programming.
#!/bin/python
import bisect
N = int(input())
s = []
x = []
length = 0
for i in range(0, N):
tmp = input().strip().split(' ')
a, b = [xx for xx in tmp]
b = int(b)
if(a=="a"):
bisect.insort(x, b)
length += 1
else:
index = bisect.bisect_left(x, b)
if index != length and x[index] == b:
del x[index]
length -=1
else:
print ("Wrong!")
continue
if(length<=0):
print ("Wrong!")
continue
nforme, nfm = divmod(length,2)
nforme -= 1
if(nfm>0):
nforme += 1
print(x[nforme])
else:
nfm = nforme + 1
median = x[nforme] + x[nfm]
median /= 2
if(round(median)==median):
median = round(median);
print(median)Problem solution in Java Programming.
import java.io.*;
import java.util.*;
import java.text.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner scanner = new Scanner(System.in) ;
Integer n = scanner.nextInt() ;
if (n < 1 || n > 100000) {
throw new IllegalArgumentException("1 <= n <= 100000") ;
}
DecimalFormat fmt = new DecimalFormat("#.#") ;
SplitedNumberSet set = new SplitedNumberSet() ;
for (int i=0;i<n;i++) {
String operation = scanner.next() ;
if (operation.equals("a") ) {
set.addNum(scanner.nextInt());
} else if (operation.equals("r")) {
if (!set.removeNum(scanner.nextInt())) {
System.out.println("Wrong!") ;
continue ;
}
} else {
throw new IllegalArgumentException("Operation must be a or r") ;
}
Double median = set.getMedian() ;
if (median != null) {
//System.out.println(fmt.format(median)+" "+set) ;
System.out.println(fmt.format(median)) ;
} else {
System.out.println("Wrong!") ;
}
}
}
private static class SplitedNumberSet {
private NumberSet smallSet = new NumberSet() ;
private NumberSet largeSet = new NumberSet() ;
public void addNum(Integer num) {
if (smallSet.getLastNum() >= num) {
smallSet.addNum(num) ;
} else {
largeSet.addNum(num) ;
}
balanceTree() ;
}
public boolean removeNum(Integer num) {
boolean removed = false ;
if (smallSet.getLastNum() >= num) {
removed = smallSet.removeNum(num) ;
} else {
removed = largeSet.removeNum(num) ;
}
if (removed) {
balanceTree() ;
}
return removed ;
}
public void balanceTree() {
if (smallSet.getNumberCnt()-largeSet.getNumberCnt()>1) {
// Push last number in smallSet to large
Integer middleNum = smallSet.getLastNum() ;
smallSet.removeNum(middleNum);
largeSet.addNum(middleNum) ;
} else if (largeSet.getNumberCnt()>smallSet.getNumberCnt()) {
// Push first number in largeSet to small
Integer middleNum = largeSet.getFirstNum() ;
largeSet.removeNum(middleNum);
smallSet.addNum(middleNum) ;
}
}
public Double getMedian() {
if (smallSet.getNumberCnt()<=0 && largeSet.getNumberCnt() <=0) {
return null ;
}
if (smallSet.getNumberCnt() > largeSet.getNumberCnt()) {
return (double)smallSet.getLastNum() ;
} else if (smallSet.getNumberCnt() < largeSet.getNumberCnt()) {
return (double)largeSet.getFirstNum() ;
} else {
return (((long)smallSet.getLastNum()+(long)largeSet.getFirstNum())/2d) ;
}
}
public String toString() {
return "small:"+smallSet+" large:"+largeSet ;
}
}
private static class NumberSet {
private SortedMap<Integer,Integer> map = new TreeMap<Integer,Integer>() ;
private int numberCnt = 0;
public void addNum(Integer num) {
if (map.containsKey(num)) {
map.put(num,map.get(num)+1) ;
} else {
map.put(num,1) ;
}
numberCnt++ ;
}
public boolean removeNum(Integer num) {
Integer current = map.get(num) ;
if (current == null) {
return false ;
}
if (current==1) {
map.remove(num) ;
} else {
map.put(num,current-1) ;
}
numberCnt-- ;
return true ;
}
public Integer getFirstNum() {
if (map.isEmpty()) {
return Integer.MIN_VALUE ;
}
return map.firstKey() ;
}
public Integer getLastNum() {
if (map.isEmpty()) {
return Integer.MAX_VALUE ;
}
return map.lastKey() ;
}
public Integer getNumberCnt() {
return numberCnt ;
}
public String toString() {
return map+":"+numberCnt ;
}
}
}Problem solution in C++ programming.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void median(vector<char> s,vector<ll> X) {
ll n=s.size();
multiset<ll> m,m1;
for(ll i=0;i<n;i++){
if(s[i]=='a'){
if(m.size()==0 || (*m.rbegin())>=X[i]){
m.insert(X[i]);
if(m.size()-m1.size()==2){
ll x=*m.rbegin();
m.erase(m.find(x));
m1.insert(x);
}
}
else {
m1.insert(X[i]);
if(m1.size()>m.size()){
ll x=*m1.begin();
m1.erase(m1.find(x));
m.insert(x);
}
}
}
else{
if(m.find(X[i])==m.end() && m1.find(X[i])==m1.end()){
cout<<"Wrong!\n";
continue;
}
else if(m.find(X[i])!=m.end()){
m.erase(m.find(X[i]));
if(m.size()<m1.size()){
ll x=*m1.begin();
m1.erase(m1.find(x));
m.insert(x);
}
}
else {
m1.erase(m1.find(X[i]));
if(m.size()-m1.size() >=2){
ll x=*m.rbegin();
m.erase(m.find(x));
m1.insert(x);
}
}
}
if(m.size()==0 && m1.size()==0) {
cout<<"Wrong!\n";
continue;
}
if(m1.size()==0){
cout<<*m.rbegin()<<endl;
continue;
}
double db=((m.size()>m1.size() ? *m.rbegin(): (*m.rbegin()+*m1.begin())/2.0));
if(ceil(db)!=db) cout<<fixed<<setprecision(1)<<db<<endl;
else cout<<fixed<<setprecision(0)<<db<<endl;
}
}
int main(void){
ll N;
cin >> N;
vector<char> s;
vector<ll> X;
char temp;
ll tempint;
for(ll i = 0; i < N; i++){
cin >> temp >> tempint;
s.push_back(temp);
X.push_back(tempint);
}
median(s,X);
return 0;
}Problem solution in C programming.
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
/* Head ends here */
void insertionSort(int N,int *x){
int temp = x[N-1];
int j=N-2;
while ( j>=0 && x[j]>temp){
x[j+1] = x[j];
j--;
}
x[j+1] = temp;
}
void median(int N,char (*s), int *x) {
int size = 0;
int a[N];
for(int i=0; i<N; i++){
if (s[i] == 'a'){
a[size++] = x[i];
insertionSort(size,&a[0]);
if (size % 2 == 1)
printf("%d",a[size/2]);
else{
if ((a[size/2]+a[(size/2)-1]) % 2 == 0)
printf("%ld",((long)a[size/2]+a[(size/2)-1])/2);
else
printf("%1.1f",((signed long)a[size/2]+a[(size/2)-1])/2.0);
}
printf("\n");
}
else{
if (size == 0) {printf("Wrong!\n");continue;}
int found = 0;
for(int j=0; j<size; j++){
if (a[j] == x[i]){
for(int k=j; k<size-1; k++){
a[k] = a[k+1];
}
size--;
if (size == 0) printf("Wrong!");
else if (size % 2 == 1)
printf("%d",a[size/2]);
else{
if ((a[size/2]+a[(size/2)-1]) % 2 == 0)
printf("%ld",((long)a[size/2]+a[(size/2)-1])/2);
else
printf("%1.1f",((signed long)a[size/2]+a[(size/2)-1])/2.0);
}
printf("\n");
found = 1;
break;
}
}
if (!found) printf("Wrong!\n");
}
}
}
int main(){
//Helpers for input/output
int i, N;
scanf("%d", &N);
char s[N];
int x[N];
for(i=0; i<N; i++){
scanf("%s %d", &(s[i]), &(x[i]));
}
median(N,s,x);
}Problem solution in JavaScript programming.
class MinHeap {
constructor() {
this.heap = [];
}
size() {
return this.heap.length;
}
insert(x) {
let i = this.heap.length;
this.heap.push(x);
this.siftUp(i);
}
pop() {
if (this.heap.length === 1) {
return this.heap.pop();
}
let top = this.heap[0];
this.heap[0] = this.heap.pop();
this.siftDown(0);
return top;
}
remove(x) {
let i = 0;
while (i < this.heap.length && this.heap[i] !== x) {
i++;
}
if (i === this.heap.length - 1) {
this.heap.pop();
return true;
}else if (i >= this.heap.length) {
return false;
}
this.heap[i] = this.heap.pop();
if (this.heap[i] < this.heap[Math.floor((i-1)/2)]) {
this.siftUp(i);
}else {
this.siftDown(i);
}
return true;
}
siftUp(i) {
while (this.heap[Math.floor((i-1)/2)] > this.heap[i]) {
let t = this.heap[Math.floor((i-1)/2)];
this.heap[Math.floor((i-1)/2)] = this.heap[i];
this.heap[i] = t;
i = Math.floor((i-1)/2);
}
}
siftDown(i) {
while ((i*2+1 < this.heap.length && this.heap[i] > this.heap[i*2+1]) ||
(i*2+2 < this.heap.length && this.heap[i] > this.heap[i*2+2])) {
let t = this.heap[i];
if (i*2+1 >= this.heap.length) {
this.heap[i] = this.heap[i*2+2];
this.heap[i*2+2] = t;
i = i * 2 + 2;
}else if (i*2+2 >= this.heap.length) {
this.heap[i] = this.heap[i*2+1];
this.heap[i*2+1] = t;
i = i * 2 + 1;
}else if (this.heap[i*2+1] <= this.heap[i*2+2]) {
this.heap[i] = this.heap[i*2+1];
this.heap[i*2+1] = t;
i = i * 2 + 1;
}else {
this.heap[i] = this.heap[i*2+2];
this.heap[i*2+2] = t;
i = i * 2 + 2;
}
}
}
peak() {
return this.heap[0];
}
check() {
for (let i = 0; i < Math.floor(this.heap.length/2); i++) {
if (this.heap[i] > this.heap[i*2+1] || this.heap[i] > this.heap[i*2+2]) {
return false;
}
}
return true;
}
}
class MaxHeap extends MinHeap {
constructor() {
super();
}
insert(x) {
let i = this.heap.length;
this.heap.push(x);
this.siftUp(i);
}
pop() {
if (this.heap.length === 1) {
return this.heap.pop();
}
let top = this.heap[0];
this.heap[0] = this.heap.pop();
this.siftDown(0);
return top;
}
remove(x) {
let i = 0;
while (i < this.heap.length && this.heap[i] !== x) {
i++;
}
if (i === this.heap.length - 1) {
this.heap.pop();
return true;
}else if (i >= this.heap.length) {
return false;
}
this.heap[i] = this.heap.pop();
if (this.heap[i] > this.heap[Math.floor((i-1)/2)]) {
this.siftUp(i);
}else {
this.siftDown(i);
}
return true;
}
siftUp(i) {
while (this.heap[Math.floor((i-1)/2)] < this.heap[i]) {
let t = this.heap[Math.floor((i-1)/2)];
this.heap[Math.floor((i-1)/2)] = this.heap[i];
this.heap[i] = t;
i = Math.floor((i-1)/2);
}
}
siftDown(i) {
while ((i*2+1 < this.heap.length && this.heap[i] < this.heap[i*2+1]) ||
(i*2+2 < this.heap.length && this.heap[i] < this.heap[i*2+2])) {
let t = this.heap[i];
if (i*2+1 >= this.heap.length) {
this.heap[i] = this.heap[i*2+2];
this.heap[i*2+2] = t;
i = i * 2 + 2;
}else if (i*2+2 >= this.heap.length) {
this.heap[i] = this.heap[i*2+1];
this.heap[i*2+1] = t;
i = i * 2 + 1;
}else if (this.heap[i*2+1] >= this.heap[i*2+2]) {
this.heap[i] = this.heap[i*2+1];
this.heap[i*2+1] = t;
i = i * 2 + 1;
}else {
this.heap[i] = this.heap[i*2+2];
this.heap[i*2+2] = t;
i = i * 2 + 2;
}
}
}
check() {
for (let i = 0; i < Math.floor(this.heap.length/2); i++) {
if (this.heap[i] < this.heap[i*2+1] || this.heap[i] < this.heap[i*2+2]) {
console.log(i, this.heap[i]);
return false;
}
}
return true;
}
}
class MedianHeap {
constructor() {
this.min = new MinHeap();
this.max = new MaxHeap();
this.size = 0;
}
size() {
return this.size();
}
insert(x) {
if (this.size === 0) {
this.min.insert(x);
}else if (this.size % 2 === 1) {
if (x > this.min.peak()) {
this.min.insert(x);
this.max.insert(this.min.pop());
}else {
this.max.insert(x);
}
}else {
if (x > this.min.peak()) {
this.min.insert(x);
}else {
this.max.insert(x);
this.min.insert(this.max.pop());
}
}
this.size++;
}
remove(x) {
if (this.min.size() > 0 && x >= this.min.peak()) {
let r = this.min.remove(x);
if (r) {
this.size--;
if (this.size % 2 === 1) {
this.min.insert(this.max.pop());
}
}
return r;
}else if (this.max.size() > 0 && x <= this.max.peak()) {
let r = this.max.remove(x);
if (r) {
this.size--;
if (this.size % 2 === 0) {
this.max.insert(this.min.pop());
}
}
return r;
}else {
return false;
}
}
median() {
if (this.size === 0) {
return 'Wrong!';
}else if (this.size % 2 === 1) {
return this.min.peak();
}else {
return this.min.peak()/2 + this.max.peak()/2;
}
}
}
function processData(input) {
let h = new MedianHeap();
input = input.split('\n');
input.shift();
for (const s of input) {
let n = parseInt(s.split(' ').pop());
if (s[0] === 'a') {
h.insert(n);
console.log(h.median());
}else {
if (h.remove(n)) {
console.log(h.median());
}else {
console.log('Wrong!');
}
}
}
}
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