Как найти пару с k-й наибольшей суммой?

Я начинаю с простого, но не вполне линейного алгоритма. Мы выбираем некоторое значение между array1[0]+array2[0] и array1[N-1]+array2[N-1] . Затем мы определяем, сколько парных сумм больше этого значения и сколько из них меньше. Это может быть сделано путем итерации массивов с помощью двух указателей: указатель на первый массив, приращенный при слишком большой сумме, и указатель на второй массив, уменьшенный, когда сумма слишком мала. Повторяя эту процедуру для разных значений и используя двоичный поиск (или односторонний бинарный поиск), мы могли бы найти наибольшую сумму Kth в O (N log R) времени, где N – размер самого большого массива, а R – количество возможных значений между array1[N-1]+array2[N-1] и array1[0]+array2[0] . Этот алгоритм имеет линейную временную сложность только тогда, когда элементы массива представляют собой целые числа, ограниченные малой константой.

Предыдущий алгоритм может быть улучшен, если мы прекращаем двоичный поиск, как только количество парных сумм в двоичном диапазоне поиска уменьшается от O (N ² ) до O (N). Затем мы заполняем вспомогательный массив этими парами сумм (это может быть сделано с помощью слегка модифицированного алгоритма с двумя указателями). И затем мы используем алгоритм quickselect для нахождения наибольшей суммы Kth в этом вспомогательном массиве. Все это не улучшает худшую сложность, поскольку нам все еще нужны шаги бинарного поиска O (log R). Что делать, если мы сохраним функцию quickselect этого алгоритма, но (чтобы получить правильный диапазон значений) мы используем что-то лучше, чем бинарный поиск?

Мы можем оценить диапазон значений с помощью следующего трюка: получить каждый второй элемент из каждого массива и попытаться найти парную сумму с рангом k/4 для этих полумассивов (используя тот же алгоритм рекурсивно). Очевидно, что это должно дать некоторое приближение для необходимого диапазона значений. И на самом деле слегка улучшенный вариант этого трюка дает диапазон, содержащий только элементы O (N). Это подтверждается в следующей статье: «Выбор в X + Y и матрицы с отсортированными строками и столбцами» А. Мирзаяна и Э. Арджоманди . В этой статье содержится подробное объяснение алгоритма, доказательства, анализа сложности и псевдокода для всех частей алгоритма, кроме Quickselect . Если требуется сложность линейного наихудшего случая, Quickselect может быть дополнен алгоритмом медианы медианов.

Этот алгоритм имеет сложность O (N). Если один из массивов короче, чем другой массив (M

Если k N (N-1), нам лучше решить противоположную задачу: k’-самую маленькую сумму.

Я загрузил простую реализацию C ++ 11 в ideone . Код не оптимизирован и не прошел тщательную проверку. Я попытался сделать это как можно ближе к псевдокоду в связанной бумаге. В этой реализации используется std::nth_element , что позволяет линейную сложность только в среднем (не в худшем случае).

Совершенно иной подход к поиску K’th суммы в линейном времени основан на очереди приоритетов (PQ). Одним из вариантов является вставка наибольшей пары в PQ, затем многократное удаление вершины PQ и вместо этого вставка до двух пар (одна с декрементированным индексом в одном массиве, другая с декрементированным индексом в другом массиве). И предпримите некоторые меры, чтобы предотвратить вставку повторяющихся пар. Другая вариация заключается в том, чтобы вставить все возможные пары, содержащие наибольший элемент первого массива, затем многократно удалять вершину PQ и вместо этого вставлять пару с декрементированным индексом в первом массиве и том же индексе во втором массиве. В этом случае нет необходимости беспокоиться о дубликатах.

OP упоминает решение O (K log K), где PQ реализуется как max-heap. Но в некоторых случаях (когда элементы массива равномерно распределены, целые числа с ограниченным диапазоном и линейной сложностью необходимы только в среднем, а не в худшем случае), мы могли бы использовать очередь приоритетов O (1), например, как описано в этой статье: Сложность O (1) Очередь приоритетов для симуляций молекулярной динамики, управляемых событиями “Джеральда Павла . Это позволяет использовать ожидаемую временную сложность O (K).

Преимуществом этого подхода является возможность предоставления первых элементов K в отсортированном порядке. Недостатками являются ограниченный выбор типа элемента массива, более сложный и медленный алгоритм, худшая асимптотическая сложность: O (K)> O (N).

EDIT: Это не работает. Я оставляю ответ, потому что, по-видимому, я не единственный, у кого могла быть такая идея; см. обсуждение ниже. Контрпример: x = (2, 3, 6), y = (1, 4, 5) и k = 3, где алгоритм дает 7 (3 + 4) вместо 8 (3 + 5).

Пусть x и y – два массива, отсортированные в порядке убывания; мы хотим построить K самую большую сумму.

Переменные: i индекс в первом массиве (элемент x[i] ), j – индекс во втором массиве (элемент y[j] ), а k – «порядок» суммы ( k в 1..K ), в том смысле, что S(k)=x[i]+y[j] будет k большей суммой, удовлетворяющей вашим условиям (это инвариант цикла).

Начнем с (i, j) равным (0, 0) : очевидно, S(1) = x[0]+y[0] .

для k от 1 до K-1 , выполните:

• если x[i+1]+ y[j] > x[i] + y[j+1] , то i := i+1 (и j не меняется); else j:=j+1

Чтобы убедиться, что это работает, считайте, что S(k) = x[i] + y[j] . Тогда S(k+1) – наибольшая сумма, которая ниже (или равна) S(k) и такая, как по крайней мере, один элемент ( i или j ) изменяется. Нетрудно видеть, что именно один из i или j должен измениться. Если i изменяется, то большая сумма, которую вы можете построить, которая меньше S(k) равна i=i+1 , так как x уменьшается, и все x[i'] + y[j] с i' < i являются больше S(k) . То же самое справедливо для j , показывая, что S(k+1) либо x[i+1] + y[j] либо x[i] + y[j+1] .

Поэтому в конце цикла вы нашли K большую сумму.

tl; dr: Если вы посмотрите вперед и посмотрите на каждую итерацию, вы можете начать с конца (что является самым высоким) и вернуться в O(K) .

Хотя понимание этого подхода, я считаю, звучит, код ниже не совсем корректен (см. Комментарии).

Давайте посмотрим: во-первых, массивы отсортированы. Итак, если массивы a и b с длинами M и N , и по мере их размещения наибольшие элементы находятся в слотах M и N соответственно, самая большая пара всегда будет a[M]+b[N] .

Теперь, какая вторая по величине пара? У него будет, возможно, один из {a[M],b[N]} (он не может иметь обоих, потому что это только самая большая пара снова) и по крайней мере один из {a[M-1],b[N-1]} . НО, мы также знаем, что если мы выберем a[M-1]+b[N-1] , мы можем сделать один из операндов большим, выбирая большее число из того же списка, поэтому он будет иметь ровно одно число из последний столбец и один из предпоследнего столбца.

Рассмотрим следующие два массива: a = [1, 2, 53]; b = [66, 67, 68] a = [1, 2, 53]; b = [66, 67, 68] . Наша самая высокая пара – 53+68 . Если мы потеряем меньшую из этих двух, наша пара равна 68+2 ; если мы потеряем больше, это 53+67 . Итак, мы должны смотреть вперед, чтобы решить, какая будет наша следующая пара. Простейшей страtagsей обзора является просто вычисление суммы обеих возможных пар. Это всегда будет стоить двух дополнений и двух сравнений для каждого перехода (три, потому что нам нужно иметь дело с случаем, когда суммы равны), назовем эту стоимость Q ).

Сначала мне захотелось повторить, что К-1 раз. НО есть заминка: следующей самой большой парой может быть другая пара, которую мы можем достоверно сделать из {{a[M],b[N]}, {a[M-1],b[N-1]} . Поэтому нам также нужно заглянуть.

Итак, давайте код (python, должен быть совместим с 2/3):

 def kth(a,b,k): M = len(a) N = len(b) if k > M*N: raise ValueError("There are only %s possible pairs; you asked for the %sth largest, which is impossible" % M*N,k) (ia,ib) = M-1,N-1 #0 based arrays # we need this for lookback nottakenindices = (0,0) # could be any value nottakensum = float('-inf') for i in range(k-1): optionone = a[ia]+b[ib-1] optiontwo = a[ia-1]+b[ib] biggest = max((optionone,optiontwo)) #first deal with look behind if nottakensum > biggest: if optionone == biggest: newnottakenindices = (ia,ib-1) else: newnottakenindices = (ia-1,ib) ia,ib = nottakenindices nottakensum = biggest nottakenindices = newnottakenindices #deal with case where indices hit 0 elif ia <= 0 and ib <= 0: ia = ib = 0 elif ia <= 0: ib-=1 ia = 0 nottakensum = float('-inf') elif ib <= 0: ia-=1 ib = 0 nottakensum = float('-inf') #lookahead cases elif optionone > optiontwo: #then choose the first option as our next pair nottakensum,nottakenindices = optiontwo,(ia-1,ib) ib-=1 elif optionone < optiontwo: # choose the second nottakensum,nottakenindices = optionone,(ia,ib-1) ia-=1 #next two cases apply if options are equal elif a[ia] > b[ib]:# drop the smallest nottakensum,nottakenindices = optiontwo,(ia-1,ib) ib-=1 else: # might be equal or not - we can choose arbitrarily if equal nottakensum,nottakenindices = optionone,(ia,ib-1) ia-=1 #+2 - one for zero-based, one for skipping the 1st largest data = (i+2,a[ia],b[ib],a[ia]+b[ib],ia,ib) narrative = "%sth largest pair is %s+%s=%s, with indices (%s,%s)" % data print (narrative) #this will work in both versions of python if ia <= 0 and ib <= 0: raise ValueError("Both arrays exhausted before Kth (%sth) pair reached"%data[0]) return data, narrative 

Для тех, у кого нет python, вот идеон: http://ideone.com/tfm2MA

В худшем случае у нас есть 5 сравнений на каждой итерации и итерации К-1, что означает, что это алгоритм O (K).

Теперь, возможно, будет возможно использовать информацию о различиях между значениями, чтобы немного оптимизировать это, но это достигает цели.

Вот ссылочная реализация (а не O(K) , но всегда будет работать, если только нет углового случая с случаями, когда пары имеют равные суммы):

 import itertools def refkth(a,b,k): (rightia,righta),(rightib,rightb) = sorted(itertools.product(enumerate(a),enumerate(b)), key=lamba((ia,ea),(ib,eb):ea+eb)[k-1] data = k,righta,rightb,righta+rightb,rightia,rightib narrative = "%sth largest pair is %s+%s=%s, with indices (%s,%s)" % data print (narrative) #this will work in both versions of python return data, narrative 

Это вычисляет декартово произведение двух массивов (т. Е. Всех возможных пар), сортирует их по сумме и принимает k-й элемент. Функция enumerate украшает каждый элемент своим индексом.

Алгоритм max-heap в другом вопросе прост, быстр и правилен. Не стучите. Это также хорошо объяснено. https://stackoverflow.com/a/5212618/284795

Может быть, нет никакого алгоритма O (k). Все в порядке, O (k log k) почти так же быстро.

Если бы последние два решения находились в (a1, b1), (a2, b2), то мне кажется, что есть только четыре возможных решения (a1-1, b1) (a1, b1-1) (a2-1, b2 ) (a2, b2-1). Эта интуиция может быть неправильной. Разумеется, для каждой координаты должно быть не более четырех кандидатов, а следующая самая высокая – среди 16 пар (a в {a1, a2, a1-1, a2-1}, b в {b1, b2, b1-1, b2- 1}). Ничего страшного).

(Нет, это не так, все еще неясно, возможно ли это.)

 [2, 3, 5, 8, 13] [4, 8, 12, 16] 

Объедините 2 массива и запишите индексы в отсортированном массиве. Вот массив индексов (начиная с 1 не 0)

[1, 2, 4, 6, 8] [3, 5, 7, 9]

Теперь начните с конца и создайте кортежи. суммируем элементы в кортеже и выбираем k-ю самую большую сумму.