Найти медиану суммы массивов

Даны два отсортированных массива длины 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) времени.

Ответы

Ответ 1

Правильное решение O (n) довольно сложно и требует значительного количества текста, кода и навыков для объяснения и доказательства. Точнее, это делает 3 страницы, чтобы сделать это убедительно, как можно подробнее увидеть здесь http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf (найденный simonzack в комментариях).

Это, в основном, умный алгоритм разделения и покоя, который, среди прочего, использует тот факт, что в отсортированной n-на-n-матрице можно найти в O(n) количество меньших элементов/больше заданного числа k. Он рекурсивно разбивает матрицу на более мелкие подматрицы (беря только нечетные строки и столбцы, что приводит к подматрице, имеющей n/2 colums и n/2 rows), которая в сочетании с вышеописанным шагом приводит к сложности O(n) + O(n/2) + O(n/4)... = O(2*n) = O(n), Это безумие!

Я не могу объяснить это лучше, чем бумага , поэтому я объясню более простое решение O(n logn):).

O (n * logn):

Это интервью! Вы не можете получить это решение O(n) вовремя. Итак, почему бы не обеспечить решение, которое, хотя и не оптимальное, показывает, что вы можете сделать лучше, чем другие очевидные кандидаты O(n²)?

Я воспользуюсь описанным выше алгоритмом O(n), чтобы найти количество чисел, которые меньше/больше заданного числа k в отсортированной матрице n-by-n. Имейте в виду, что нам не нужна настоящая матрица! Декартова сумма двух массивов размера n, как описано OP, приводит к сортированной матрице n-by-n, которую мы можем моделировать, рассматривая элементы массива следующим образом:

a[3] = {1, 5, 9};
b[3] = {4, 6, 8};
//a + b:
{1+4, 1+6, 1+8,
 5+4, 5+6, 5+8,
 9+4, 9+6, 9+8}

Таким образом, каждая строка содержит неубывающие числа, а также каждый столбец. Теперь притворись, что тебе присвоен номер k. Мы хотим найти в O(n), сколько чисел в этой матрице меньше, чем k, и сколько их больше. Ясно, что если оба значения меньше (n²+1)/2, это означает, что k является нашей медианой!

Алгоритм довольно прост:

int smaller_than_k(int k){
    int x = 0, j = n-1;
    for(int i = 0; i < n; ++i){
        while(j >= 0 && k <= a[i]+b[j]){
            --j;
        }
        x += j+1;
    }
    return x;
}

Это в основном подсчитывает, сколько элементов соответствует условию в каждой строке. Поскольку строки и столбцы уже отсортированы, как показано выше, это даст правильный результат. И поскольку оба i и j повторяют не более n раз каждый, алгоритм O(n) [Обратите внимание, что j не получает reset в цикле for]. Алгоритм greater_than_k аналогичен.

Теперь, как мы выбираем k? Это часть logn. Двоичный поиск! Как уже упоминалось в других ответах/комментариях, медиана должна быть значением, содержащимся в этом массиве:

candidates[n] = {a[0]+b[n-1], a[1]+b[n-2],... a[n-1]+b[0]};.

Просто отсортируйте этот массив [также O(n*logn)] и запустите на нем двоичный поиск. Поскольку массив теперь находится в неубывающем порядке, он прямо заметил, что количество чисел, меньших, чем каждый candidate[i], также является неубывающим значением (монотонная функция), что делает его подходящим для двоичного поиска. Наибольшее число k = candidate[i], результат которого smaller_than_k(k) возвращает меньше, чем (n²+1)/2, является ответом и получен в log(n) итерациях:

int b_search(){
    int lo = 0, hi = n, mid, n2 = (n²+1)/2;
    while(hi-lo > 1){
        mid = (hi+lo)/2;
        if(smaller_than_k(candidate[mid]) < n2)
            lo = mid;
        else
            hi = mid;
    }
    return candidate[lo]; // the median
}

Ответ 2

Пусть говорят, что массивы A = {A[1] ... A[n]} и B = {B[1] ... B[n]}, а парный массив сумм - C = {A[i] + B[j], where 1 <= i <= n, 1 <= j <= n}, который имеет элементы n^2, и нам нужно найти его медиану.

Медиана C должна быть элементом массива D = {A[1] + B[n], A[2] + B[n - 1], ... A[n] + B[1]}: если вы исправите A[i] и рассмотрите все суммы A[i] + B[j], вы увидите, что только A[i] + B[j = n + 1 - i] (который является одним из D) может быть медианным. То есть, это может быть не медиана, но если это не так, то все остальные A[i] + B[j] также не являются медианными.

Это можно доказать, рассмотрев все B[j] и подсчитав количество ниже и количество значений больше, чем A[i] + B[j] (мы можем сделайте это довольно точно, потому что два массива отсортированы - расчет - немного грязная мысль). Вы увидите, что для A[i] + B[n + 1 - j] эти два счета наиболее "сбалансированы".

Затем проблема сводится к нахождению медианы D, которая имеет только элементы n. Будет работать алгоритм Hoare.

ОБНОВЛЕНИЕ: этот ответ неверен. Реальный вывод здесь состоит в том, что медиана является одним из элементов D, но тогда D медиана - это не то же самое, что C медиана.

Ответ 3

Разве это не работает?:

Вы можете вычислить ранг числа в линейном времени, пока сортируются A и B. Техника, используемая для вычисления ранга, также может использоваться для поиска всех вещей в A+B, которые находятся между некоторой нижней границей и некоторой верхней границей во времени, линейной размером вывода плюс |A|+|B|.

Случайно выберите n вещи из A+B. Возьмите медианную, скажем foo. Вычислить ранг foo. При постоянной вероятности ранг foo находится в пределах n медианного ранга. Продолжайте делать это (ожидаемое постоянное количество раз) до тех пор, пока вы не получите нижнюю и верхнюю границы медианы, находящиеся в пределах 2n друг от друга. (Весь этот процесс требует ожидаемого линейного времени, но он явно замедляется.)

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

(Безразлично, я бы не стал извиняться интервьюеру за то, что он задал такой вопрос с дерьмовым интервью. Такие вещи никоим образом не указывают на вашу способность кодировать.)

EDIT. Вы можете вычислить ранг числа x, выполнив что-то вроде этого:

Set i = j = 0.
While j < |B| and A[i] + B[j] <= x, j++.
While i < |A| {
  While A[i] + B[j] > x and j >= 0, j--.
  If j < 0, break.
  rank += j+1.
  i++.
}

ДАЛЬНЕЙШЕЕ ИЗОБРАЖЕНИЕ. На самом деле вышеупомянутый трюк только сужает пространство кандидатов примерно до n log (n) членов A+B. Тогда у вас есть общая проблема выбора в юниверсе размера n log (n); вы можете сделать один и тот же трюк еще раз и найти диапазон размеров, пропорциональный sqrt (n) log (n), где вы делаете выделение.

Вот почему: Если вы отбираете k вещей из n-множества и принимаете медианную, то средний медианный порядок находится между (1/2 - sqrt (log (n)/k)) th и (1/2 + sqrt (log (n)/k)) -й элементов с по меньшей мере постоянной вероятностью. Когда n = | A + B |, мы хотим взять k = sqrt (n), и мы получим диапазон около элементов sqrt (n log n) --- о | A | log | A |. Но тогда вы делаете это снова, и вы получаете диапазон порядка srp (n) polylog (n).