Как найти k-е наибольшее число в попарных суммах, таких как setA + setB?

Question

Вот два целых числа, скажем, A и B и мы можем получить другой набор C, в котором каждый элемент является суммой элемента a в A и элемента b в B.

Например, A = {1,2}, B = {3,4}, и мы получаем C = {4, 5, 6}, где 4 = 1 + 3 ， 5 = 1 + 4 = 2 + 3, 6 = 2 + 4

Теперь я хочу выяснить, какое число является k-ым по величине в множестве C, например, 5 является вторым по величине в приведенном выше примере.

Есть ли эффективное решение?

Я знаю, что попарная сортировка сумм является открытой проблемой и имеет ограничение по времени n ^ 2. Но так как требуется только k-е наибольшее число, возможно, мы можем извлечь из алгоритма O (n) нахождение медианного числа в несортированном массиве.

Спасибо.

Answer 1

Если k очень близко к 1 или N, любой алгоритм, который генерирует отсортированные суммы лениво, может просто выполняться, пока не появится k-й или N-й элемент.

В частности, я имею в виду поиск наилучшего первого в следующем пространстве: (a, b) означает элемент ath из A, первый список, добавленный к bth из B, второй.

Хранить в лучшем = пары очередей с самым низким приоритетом (a, b) со стоимостью (a, b) = A [a] + B [b].

Начните с просто (1,1) в очереди приоритетов, что является минимумом.

Repeat until k items popped: 
 pop the top (a,b)
 if a<|A|, push (a+1,b)
 if a=1 and b<|B|, push (a,b+1)

Это дает вам соединение с зубчатым гребнем и избавляет вас от необходимости отмечать каждый (a, b) посещенный в массиве. Обратите внимание, что стоимость (a + 1, b)> = стоимость (a, b) и стоимость (a, b + 1)> = стоимость (a, b), потому что A и B отсортированы.

Вот изображение гребня, на котором показано правило генерации преемника выше (вы начинаете в верхнем левом углу; a - горизонтальное направление):

|-------
|-------
|-------

Это просто лучшее первое исследование (до) всех | A | * | B | кортежи и их суммы.

Обратите внимание, что наиболее вероятные элементы, помещаемые перед выталкиванием k, равны 2 * k, поскольку каждый элемент имеет 1 или 2 преемника. Вот возможное состояние очереди, когда элементы, помещенные в очередь, помечены *:

|--*----
|-*-----
*-------

Все выше и слева от границы * уже вытолкнуто.

Для случая N-k<k сделайте то же самое, но с обратным порядком очередности приоритетов и порядком исследования (или, просто отрицайте и меняйте значения, получите наименьшее (Nk) число, затем отрицайте и возвращайте ответ).

См. Также: отсортированный список парных сумм на SO или Проект открытых задач .

Answer 2

Сортировка массивов A и B: O (mlogm + nlogn) Примените модифицированную форму алгоритма для объединения 2 отсортированных массивов: O (m + n) в каждой точке вы суммируете два элемента. Когда у вас есть (m + n-k + 1) -й элемент в C, прекратите слияние. Этот элемент по существу k-й по величине. Например. {1,2} & {3,4}: отсортировано C: {1 + 3, (1 + 4) | (2 + 3), 2 + 4}

Answer 3

Ну, O (n) будет нижней границей (хотя, вероятно, не жесткой), в противном случае вы можете запустить алгоритм O (n) n раз, чтобы получить отсортированный список в O (n ^ 2).

Можете ли вы предположить, что два набора отсортированы (вы представляете их в порядке сортировки выше)? Если это так, вы могли бы получить что-то со средним случаем, что прилично лучше, сделав «ранний выход», начав с последней пары элементов и т. Д. Просто догадка.