Как найти среднее из верхней половины N чисел?

Question

Учитывая N произвольных целых чисел, как найти среднее из верхней половины этих чисел? Есть ли решение O (n)? Если нет, то можно ли доказать, что это невозможно?

Answer 1

Сначала найдите медиану данного массива (это занимает линейное время ).

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

Подсчитайте, сколько элементов вы суммировали (M). Если M < N/2, то это означает, что несколько элементов, которые равны медианному значению (а именно, N/2 - M), принадлежат верхней половине. Добавьте к своей сумме столько средних значений. Нам нужна эта сложность, потому что мы не знаем, сколько медианных элементов (их может быть несколько) принадлежит верхней половине: если мы возьмем их все, мы можем в итоге сложить более N/2 элементов.

Теперь у вас есть сумма верхней половины массива. Разделите на N/2, и все готово.

Answer 2

Вы можете использовать приоритетную очередь. Вставьте элементы в очередь, ведя подсчет того, сколько элементов вы видели, n. Извлеките n/2 максимум элементов из очереди в аккумулятор и вычислите среднее.

С хорошо выбранной структурой данных позади очереди, такой как куча Фибоначчи, это даст вам O(n log n) время выполнения, поскольку вставка O(1) и извлечение O(log n).

К сожалению, не та среда исполнения O (n), которую вы искали, но с уже реализованной структурой данных это дало бы очень понятный и понятный код.

Answer 3

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

Answer 4

Я бы предложил это:

Используйте Quicksort, выберите некоторую опору.Это разделит ваш список на два подсписка, один меньший, чем сводный, один больший, чем этот.Если размер меньшего подсписка равен <= N / 2, вычислите среднее значение, скажем, <code>a1.
Если size == N/2 or size == N/2 -1
, то вы сразу же закончите.общий размер - N / 2.

Если размер> N / 2, разделите меньший подсписок.

Повторите все до конца.

PS: сортировать не нужно.