Написать функцию для нахождения медианы в потоке чисел.

Практические упражнения Python 

Выберете уровень:
►► ►► ►►►
Начальный  Средний  Высокий 

Функция для нахождения медианы в потоке чисел

Эта функция позволяет находить медиану в потоке чисел, используя две кучи (минимальную и максимальную), чтобы поддерживать балансированный доступ к медианному значению в любой момент.

import heapq

class MedianFinder:
    def __init__(self):
        # Мин-куча для хранения наибольших значений
        self.min_heap = []
        # Макс-куча для хранения наименьших значений
        self.max_heap = []

    def addNum(self, num):
        # Добавляем в макс-кучу
        heapq.heappush(self.max_heap, -num)

        # Балансировка куч
        if (self.max_heap and self.min_heap and
            (-self.max_heap[0]) > self.min_heap[0]):
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))

        # Поддержание баланса размеров куч
        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        if len(self.min_heap) > len(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def findMedian(self):
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        else:
            return (-self.max_heap[0] + self.min_heap[0]) / 2

# Пример использования:
mf = MedianFinder()
mf.addNum(1)
mf.addNum(2)
print(mf.findMedian()) # Выводит 1.5
mf.addNum(3)
print(mf.findMedian()) # Выводит 2

Класс MedianFinder использует две кучи для хранения элементов. Максимальная куча хранит наименьшие значения, а минимальная куча — наибольшие. Добавление элемента и нахождение медианы выполняются за логарифмическое время.

Категория: Практические упражнения Python | Добавил: Admin (28.04.2024)
Просмотров: 25 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *: