Сгенерированные случайным образом числа передаются методу. Напишите программу расчета медианы, динамически отслеживающую новые поступающие значения

Отредактировано

4К открытий4К показов

Одно из возможных решений — использовать две кучи разных приоритетов: максимальная куча (maxHeap) для значений выше среднего и минимальная куча (minHeap) для значений ниже среднего. Это позволит разделить элементы примерно поровну с двумя значениями — вершинами куч. Теперь найти среднее значение очень просто.

Что означает «примерно поровну»? «Примерно» означает, что при нечетном количестве чисел в одной из куч окажется лишнее число. Можно сформулировать:

			если maxHeap.size() > min.Heap.size(), то heap1.top() будет средним значением;
если maxHeap.size() == minHeap.size(), то средним значением будет среднее значений maxHeap.top() и min.Heap.top().

В алгоритме с балансировкой мы гарантируем, что maxHeap будет всегда содержать дополнительный элемент.

Алгоритм работает следующим образом. Если новое значение меньше или равно среднему, оно помещается в maxHeap, в противном случае оно попадает в minHeap. Размеры куч могут совпадать или в maxHeap может быть один дополнительный элемент. Это требование легко выполнить, сдвигая элемент из одной кучи в другую. Среднее значение находится в вершине. Обновления занимают O(log(n)) времени.

			private Comparator<Integer> maxHeapComparator;
private Comparator<Integer> minHeapComparator;
private PriorityQueue<Integer> maxHeap, minHeap;

public void addNewNumber(int randomNumber) {
	/*Заметьте: addNewNumber поддерживает условие, что
	*maxHeap.size() >= minHeap.size() */
	if (maxHeap.size() >= minHeap.size()) {
		if ((minHeap.peek() != null) &&
		randomNumber > minHeap.peek()) {
			maxHeap.offer(minHeap.poll());
			minHeap.offer(randomNumber);
		} else {
			maxHeap.offer(randomNumber);
		}
	} else {
		if(randomNumber < maxHeap.peek()) {
			minHeap.offer(maxHeap.poll());
			maxHeap.offer(randomNumber)
		}
		else {
		minHeap.offer(randomNumber);
		}
	}
}

public static double getMedian() {
	/*maxHeap является всегда по крайней мере столь же большой,
	*как minHeap. Если maxHeap пуста, то minHeap тоже пуста. */
	if (maxHeap.isEmpty()) {
		return 0;
	}
	if(maxHeap.size() == minHeap.size()) {
		return ((double)minHeap.peek()+(double)maxHeap.peek()) / 2;
	} else {
		/* Если maxHeap и minHeap разных размеров, то 
		* в maxHeap есть один дополнительный элемент.
		* Возвращаем вергину кучи maxHeap */
		return maxHeap.peek();
	}
}

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»

Задачи повышенной сложностиПодписаться

4К открытий4К показов