Запросы для вычисления среднего значения массива после удаления K наименьших и наибольших элементов с обновлениями

Опубликовано: 22 Сентября, 2022

Имея два положительных целых числа N и K , инициализируйте пустой массив arr[] и количество Q запросов следующих двух типов:

  • addInteger(x): вставить элемент X в массив arr[] . Если размер массива становится больше N , то удаляем элемент из начала массива.
  • calculateSpecialAverage(): найти среднее значение элементов массива после удаления первых K самых маленьких и самых больших элементов. Если размер массива меньше, чем N , затем выведите -1 .

Задача состоит в том, чтобы обработать заданные запросы и соответствующим образом вывести результаты.

Примеры:

Input: N = 3, K = 1, Q = 5, Queries[] = { addInteger(4), addInteger(2), calculateSpecialAverage(), addInteger(10), calculateSpecialAverage() }
Output: -1, 4
Explanation:
Below are the queries performed:
Query 1 is to insert element 4 in the array, arr[] becomes {4}.
Query 2 is to insert the element 2 in the array, arr[] becomes {4, 2}.
Query 3 is to find the average. Since the size of the array is less than N(= 3), print -1.
Query 4 is to insert the element 10 in the array, arr[] becomes {4, 2, 10}.
Query 5 is to find the average. Since the size of the array =3, remove K(= 1) the smallest element i.e., 2 and then remove the largest element i.e., 10. Now the average will be 4/1 = 4.

Input: N = 3, K = 1, Q = 5, Queries[] = { addInteger(4), addInteger(21), calculateSpecialAverage() }
Output: -1

Подход: Данную задачу можно решить с помощью мультимножества. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте три мультимножества слева, справа и посередине , чтобы сохранить K наименьшего, K наибольшего и оставшиеся (N – 2*K) целые числа.
  • Объявите вектор v размера N для хранения последних N целых чисел.
  • Объявите целочисленную переменную pos для отслеживания текущего индекса и целочисленную сумму для хранения суммы значений в середине мультимножества, которая является желаемой суммой для вычисления среднего из (N – 2*K) целых чисел.
  • Определите функцию add для вставки целого числа в левый, средний или правый мультимножество в зависимости от его значения. Чтобы вставить целое число в правильный мультимножество, выполните следующие действия:
    • Сначала вставьте целое число в левый мультимножество.
    • Если размер левого мультимножества превышает k , удалите наибольшее целое число из левого мультимножества и вставьте его в среднее мультимножество.
    • Если размер среднего мультимножества превышает (n – 2*k) , удалите наибольшее целое число из среднего мультимножества и вставьте его в правый мультимножество.
    • При удалении и добавлении целых чисел в середине мультимножества сохраняйте правильное значение суммы , т.е. если целое число удаляется из среднего мультимножества, вычтите его значение из суммы и аналогичным образом, если целое число добавляется в средний мультимножество, добавьте его значение к сумме , чтобы сохранить значение суммы обновлено.
  • Объявите функцию удаления , чтобы стереть целые числа из левого, правого или среднего мультимножества.
    • Если значение целого числа меньше или равно наибольшему целому числу в левом мультимножестве, то найдите и сотрите целое число из левого мультимножества, в противном случае найдите его в среднем или правом мультимножестве на основе его значения.
    • Если после удаления num размер левый мультимножество уменьшается, удалите наименьшее целое число из средний мультисет и вставьте его в левый мультисет.
    • Точно так же для среднего мультимножества, если размер уменьшается, удалите наименьшее целое число из правильный мультимножество и вставьте его в средний мультисет.
  • Определите функцию addInteger для добавления целого числа в текущий поток:
    • Если количество целых чисел в текущем потоке (сумма размера левого, среднего, правого мультимножества) превышает n , удалите целое число по индексу pos%n .
    • Вызовите функцию add , чтобы вставить целое число в левый, средний или правый мультимножество в зависимости от его значения.
  • Определите функцию calculateSpecialAverage , чтобы она возвращала специальное среднее значение:
    • Если количество целых чисел в потоке меньше N , то выведите -1 .
    • В противном случае выведите среднее значение как (сумма/(N – 2*K)) .

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

Временная сложность: O(log N) для addInteger() и O(1) для calculateSpecialAverage()
Вспомогательное пространство: O(N)

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