Это сообщение является кросс-постом здесь .
Предположим, что 
и 
и
Я хочу найти медиану следующего набора,
Я уже знаю две вещи,
- Существуют алгоритмы и методы для нахождения медианы несортированного массива в более или менее наихудшем времени выполнения
O(n). Самый простой способ - просто отсортировать набор и найти среднее число в O(nlog(n)). - Set
не является монотонным.
Есть ли у кого-нибудь идеи вычислить медиану каким-либо более быстрым способом? (Как сложение, вычитание или умножение определенного числа на некоторые элементы и сделать его монотонным?!)