4 эффективных метода поиска медианы из потока данных

  1. Метод 1: сортировка

    • Поддерживайте список или массив для хранения потока данных.
    • Каждый раз при поступлении нового значения вставляйте его в соответствующую позицию в отсортированном списке.
    • Если количество элементов нечетное, медианой является средний элемент. Если оно четное, медиана представляет собой среднее арифметическое двух средних элементов.

  2. Метод 2: две кучи

    • Используйте две кучи: максимальную и минимальную, для хранения нижней и верхней половины потока данных соответственно.
    • Убедитесь, что разница в размерах между двумя кучами не превышает 1.
    • Медиана может быть получена путем сравнения корневых элементов двух куч.

  3. Метод 3: двоичное дерево поиска (BST)

    • Поддерживайте сбалансированное двоичное дерево поиска для хранения потока данных.
    • Каждый узел в BST должен хранить размер своего поддерева.
    • Пройдите по BST, чтобы найти узлы, представляющие медиану.

  4. Метод 4: отбор проб из резервуара

    • Используйте метод отбора проб из резервуара, чтобы случайным образом выбрать подмножество элементов из потока данных.
    • По ходу потока обновляйте выбранное подмножество, чтобы сохранить объективную оценку медианы.