# Untitled

unknown
plain_text
2 years ago
3.2 kB
3
Indexable
Never
```import java.io.*;
import java.util.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Pair implements Comparable<Pair> {
int val;
int i;

Pair(int val, int i) {
this.val = val;
this.i = i;
}

public int compareTo(Pair b) {
if (this.val != b.val) {
return (b.val < this.val) ? 1 : -1;
}

if (b.i == this.i) {
return 0;
}

return (b.i < this.i) ? 1 : -1;
}
}

class Result {
public static List<Double> runningMedian(List<Integer> a) {
// Map to store values and their occurences
HashMap<Integer, Integer> values = new HashMap<>();
ArrayList<Double> medians = new ArrayList<>();
TreeSet<Pair> tree = new TreeSet<>();

//Set the occurences to 0
for (int x : a) {
values.put(x, 0);
}

//Init the current median
Pair median = new Pair(0, 0);

for (int i = 1; i <= a.size(); i++) {
int x = a.get(i - 1);

//Update its ocurrences in map
values.put(x, values.get(x) + 1);

Pair newPair = new Pair(x, values.get(x));

//Update the median according to the new pair
if (i % 2 == 0) {
// New pair < median
if (median.compareTo(newPair) == 1) {
median = tree.lower(median);
}

} else {
// Median < new pair
if (newPair.compareTo(median) == 1) {
median = tree.higher(median);
}

}
}

return medians;
}

}

public class Solution {
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

List<Integer> a = IntStream.range(0, aCount).mapToObj(i -> {
try {
} catch (IOException ex) {
throw new RuntimeException(ex);
}
})
.map(String::trim)
.map(Integer::parseInt)
.collect(toList());

List<Double> result = Result.runningMedian(a);

bufferedWriter.write(
result.stream()
.map(Object::toString)
.collect(joining("\n"))
+ "\n"
);