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