Медиана текущего потока чисел - (с использованием набора)

Опубликовано: 2 Декабря, 2021

Учитывая, что целые числа читаются из потока данных. Найдите медиану всех прочитанных элементов, начиная с первого целого числа до последнего целого числа. Это также называется медианой бегущих целых чисел.
По данной ссылке уже есть решение этой проблемы с использованием Priority Queue.
Однако в следующем решении используется та же концепция, но реализация осуществляется с помощью наборов.
В этом решении мы будем печатать меньшую медиану в случае четной длины вместо их среднего.

Примеры:

Input: arr[] = {-10, 14, 11, -5, 7}
Output: -10 -10 11 -5 7
Input: arr[] = {2, -5, 14}
Output: 2 -5 2

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

Создайте два мультимножества g в возрастающем порядке, в которых будет храниться верхняя половина, и s в порядке убывания, чтобы сохранить нижнюю половину массива arr [] .
Вставьте первый элемент в s . И инициализируйте медиану этим значением.
Для каждого другого элемента массива x . Проверьте размеры обоих наборов:
- Когда size (s)> size (g) : если x> median, тогда вставьте первый элемент s в g и удалите этот элемент из s , вставьте x в s . В противном случае вставьте x в g .
- Когда size (s) <size (g) : Если x <median, тогда вставьте первый элемент g в s и удалите этот элемент из g , вставьте x в g . В противном случае вставьте x в s .
- Когда размер (а) = размер (г) : Если x> медианы . Вставьте x в s . В противном случае вставьте x в g .

Ниже представлена реализация описанного выше подхода:

 // C++ program to find running median for
 // a stream of integers using Set
 #include <bits/stdc++.h>
 using namespace std;
 
// Function to print the running median
 // for the array arr[]
 void printRunningMedian( int arr[], int n)
 {
    // Multiset is used to handle duplicates
    // Multiset g for storing upper half
    // (ascending order)
    // The first element will be the smallest)
    multiset< int > g;
 
    // Multiset s for storing lower half
    // (descending order). The first element
    // will be the largest
    multiset< int , greater< int > > s;
 
    s.insert(arr[0]);
 
    // Initialise median with the first element
    int med = arr[0];
    printf ( "%d " , med);
 
    for ( int i = 1; i < n; i++) {
 
        // Only add elements to upper half if
        // its size less then the size of the
        // lower half (maintain only difference
        // of 1)
        if (s.size() > g.size()) {
            if (arr[i] < med) {
                int temp = *s.begin();
                s.erase(s.begin());
                g.insert(temp);
                s.insert(arr[i]);
            }
            else
                g.insert(arr[i]);
 
            med = *s.begin() > *g.begin() ?
                   *g.begin() : *s.begin();
        }
 
        // Only add elements to lower half if
        // it's size less then the size of the
        // upper half (maintain only difference
        // of 1)
        else if (s.size() < g.size()) {
            if (arr[i] > med) {
                int temp = *g.begin();
                g.erase(g.begin());
                s.insert(temp);
                g.insert(arr[i]);
            }
            else
                s.insert(arr[i]);
 
            med = *s.begin() > *g.begin() ?
                   *g.begin() : *s.begin();
        }
 
        // If sizes are same
        else {
            if (arr[i] > med) {
                g.insert(arr[i]);
                med = *g.begin();
            }
            else {
                s.insert(arr[i]);
                med = *s.begin();
            }
        }
 
        printf ( "%d " , med);
    }
 
    printf ( "
" );
 }
 
// Driver code
 int main()
 {
    int arr[] = { -10, 14, 11, -5, 7 };
    int n = sizeof (arr) / sizeof (arr[0]);
    printRunningMedian(arr, n);
    return 0;
 }

Выход:

-10-10 11-5 7

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Олимпиады по программированию Алгоритмы

Медиана текущего потока чисел - (с использованием набора)

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

РЕКОМЕНДУЕМЫЕ СТАТЬИ