Даны два отсортированных массива длины n, и вопрос заключается в том, чтобы найти в O (n) время медиану их массива сумм, которая содержит все возможные попарные суммы между каждым элементом массива A и каждым элементом массива Б.
Например: пусть A [2,4,6] и B [1,3,5] - два заданных массива.
Суммарный массив равен [2+1,2+3,2+5,4+1,4+3,4+5,6+1,6+3,6+5]
. Найдите медиану этого массива в O (n).
Решение вопроса в O (n ^ 2) довольно прямолинейно, но существует ли какое-либо решение O (n) этой проблемы?
Примечание. Это вопрос интервью, заданный одному из моих друзей, и интервьюер был совершенно уверен, что его можно решить в O (n) времени.