Ответ 1
(Это обобщение вашей идеи для двух массивов.)
Если вы начнете с рассмотрения пяти медианов пяти массивов, очевидно, общая медиана должна быть между наименьшей и самой большой из пяти медиан.
Доказательство выглядит примерно так: если a - это мин медианов, а b - максимальный размер медианы, то каждый массив имеет менее половины его элементов, меньших a, и менее половины его элементов больше b, Результат следует.
Итак, в массиве, содержащем a, выкидывайте числа, меньшие a; в массиве, содержащем b, отбросьте числа, превышающие b... Но выкиньте только одно количество элементов из обоих массивов.
То есть, если a является j элементами из начала его массива, а b является k элементами из конца его массива, вы выбрасываете первые элементы min (j, k) из массива и последний min ( j, k) элементов из массива b.
Итерации, пока вы не достигнете 1 или 2 элемента.
Каждая из этих операций (т.е. поиск медианы отсортированного массива и отбрасывание k элементов из начала или конца массива) является постоянным временем. Поэтому каждая итерация - это постоянное время.
Каждая итерация отбрасывает (более) половину элементов из по меньшей мере одного массива, и вы можете делать только это log (n) раз для каждого из пяти массивов... Таким образом, общий алгоритм - log (n).
[Обновление]
Как отмечает Химадри Чоудхури в комментариях, мое решение является неполным; есть много деталей и угловых дел, о которых нужно беспокоиться. Итак, чтобы немного поразмыслить...
Для каждого из пяти массивов R определите его "нижнюю медиану" как R [n/2-1] и ее "верхнюю медиану" как R [n/2], где n - количество элементов в массиве (и массивы индексируются от 0 и делятся на 2 раунда вниз).
Пусть "a" - наименьшая из нижних медианов, а "b" - самая большая из верхних медианов. Если имеется несколько массивов с наименьшим средним и/или несколькими массивами с наибольшей верхней средой, выберите a и b из разных массивов (это один из этих угловых случаев).
Теперь, заимствуя предложение Himadri: Удалите все элементы до и включите их из своего массива и все элементы до и включите b из своего массива, стараясь удалить одинаковое количество элементов из обоих массивов. Обратите внимание, что a и b могут находиться в одном массиве; но если это так, они не могут иметь одинаковое значение, потому что в противном случае мы могли бы выбрать один из них из другого массива. Итак, это нормально, если этот шаг завершает выброс элементов из начала и конца одного и того же массива.
Итерируйте, если у вас есть три или более массивов. Но как только вы попадаете в один или два массива, вы должны изменить свою стратегию как эксклюзивную, а не включительную; вы только стираете до, но не включая a и вниз, но не включая b. Продолжайте так, пока оба оставшихся одного или двух массивов имеют по крайней мере три элемента (гарантируя, что вы достигнете прогресса).
Наконец, вы уменьшите до нескольких случаев, самым сложным из которых является оставшееся два массива, один из которых имеет один или два элемента. Теперь, если бы я спросил вас: "Учитывая отсортированный массив плюс один или два дополнительных элемента, найдите медиану всех элементов", я думаю, вы можете сделать это в постоянное время. (Опять же, есть куча деталей, чтобы выработать молот, но основная идея состоит в том, что добавление одного или двух элементов в массив не очень сильно "выталкивает медианную область".)