Интервью:
Отредактировано ниже Вам задан массив. Вы делаете из него 2 кучи, один мины и другую максимальную кучу. Теперь найдите медиану массива, используя эти 2 предоставленные кучи в O (nlog n) времени.
Исправленный вопрос Числа генерируются случайным образом и сохраняются в (расширяющемся) массиве. Как вы будете отслеживать медианную?
Решение Эта проблема может быть решена с использованием двух кучек, и медиана всегда может быть доступна в течение O (1).
Вот как вы используете обе кучи. Обратите внимание, что я предполагаю, что вы не знаете количество элементов, и поэтому мы должны появляться до тех пор, пока мы не вытащим что-то из кучи min, которая больше или равна тому, что мы выталкиваем из максимальной кучи. Обратите внимание, что мы возвращаем среднее значение, потому что в случае набора, подобного {1, 2, 3, 4}, медиана на самом деле 2.5 (среднее значение двух средних значений). Я предполагаю double как тип значения, но это, очевидно, может быть чем угодно. Здесь:
double min = minheap.pop();
double max = maxheap.pop();
while(min < max) {
min = minheap.pop();
max = maxheap.pop();
}
return (min + max) / 2;
Так как popping имеет значение O(log n), и нам нужно вывести значения O(n / 2), это O(n log n).
Рабочая реализация в java, используя 2 кучи, O (n log n). В любой момент я сохраняю две кучи сбалансированными по размеру (то есть они отличаются не более чем на 1, если мы ввели n элементов, таких, что n% 2 == 1). Получение медианы - O (1). Добавление нового элемента - O (log n).
public class MedianOfStream {
private int count;
private PriorityQueue<Integer> highs, lows;
public MedianOfStream() {
highs = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg0.compareTo(arg1);
}
});
lows = new PriorityQueue<Integer>(11, new Comparator<Integer>() {
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1.compareTo(arg0);
}
});
}
private int getMedian() {
if (count == 0)
return 0;
if (lows.size() == highs.size()) {
return (lows.peek() + highs.peek()) / 2;
} else if (lows.size() < highs.size()) {
return highs.peek();
}
return lows.peek();
}
private void swap(){
int h = highs.poll();
int l = lows.poll();
highs.add(l);
lows.add(h);
}
public int updateMedian(int n) {
count++;
if (count == 1)
lows.add(n);
else if (count==2) {
highs.add(n);
if(highs.peek()<lows.peek()) {
swap(); // O(log n)
}
}
else {
if (n > highs.peek()) {
lows.add(highs.poll()); // O(log n)
highs.add(n); // O(log n)
} else {
highs.add(lows.poll()); // O(log n)
lows.add(n); // O(log n)
}
if(highs.peek()<lows.peek()) {
swap(); // O(log n)
}
}
// if we added an even # of items,
// the heaps must be exactly the same size,
// otherwise we tolerate a 1-off difference
if (Math.abs(lows.size() - highs.size()) > (count % 2)) {
if (lows.size() < highs.size()) {
lows.add(highs.poll()); // O(log n)
} else {
highs.add(lows.poll()); // O(log n)
}
}
return getMedian(); // O(1)
}
}
Попадание из кучи - это операция O (log N), поэтому вы можете достичь O (N log N), выбирая половину элементов из одной из кучек и беря последнее значение (вам придется обрабатывать край случаев). Однако это не использует другую кучу.
Вы можете достичь O (N) с помощью алгоритма , но постоянный коэффициент очень высок. Предыдущее предложение, вероятно, лучше, если у вас уже есть куча.
JavaScript-решение с использованием двух куч:
function addNewNumber(minHeap, maxHeap, randomNumber) {
if (maxHeap.size() === minHeap.size()) {
if (minHeap.peek() && randomNumber > minHeap.peek()) {
maxHeap.insert(minHeap.remove());
minHeap.insert(randomNumber);
} else {
maxHeap.insert(randomNumber);
}
} else {
if (randomNumber < maxHeap.peek()) {
minHeap.insert(maxHeap.remove());
maxHeap.insert(randomNumber);
} else {
minHeap.insert(randomNumber);
}
}
}
function getMedian(minHeap, maxHeap) {
if (!maxHeap.size()) {
return 0;
}
if (minHeap.size() === maxHeap.size()) {
return (minHeap.peek() + maxHeap.peek()) / 2;
} else {
return maxHeap.peek();
}
}