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

Ответ 1

Я начинаю с простого, но не вполне линейного алгоритма. Мы выбираем какое-то значение между 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 < N), мы можем предположить, что этот более короткий массив расширяется до размера N с помощью очень маленьких элементов, так что все вычисления в алгоритме используют размер самого большого массива. Нам действительно не нужно извлекать пары с этими "добавленными" элементами и кормить их, чтобы ускорить выбор, что делает алгоритм немного быстрее, но не улучшает асимптотическую сложность.

Если k < N мы могли бы игнорировать все элементы массива с индексом, большим, чем k. В этом случае сложность равна O (k). Если N < k < N (N-1) у нас просто сложнее, чем запрошено в OP. Если k > N (N-1), нам лучше решить противоположную задачу: k'-наименьшая сумма.

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

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

OP упоминает решение O (K log K), где PQ реализуется как max-heap. Но в некоторых случаях (когда элементы массива равномерно распределены, целые числа с ограниченным диапазоном и линейной сложностью необходимы только в среднем, а не в худшем случае), мы могли бы использовать очередь приоритетов O (1), например, как описано в этой статье: a href= "http://arxiv.org/pdf/physics/0606226" > "Очередь приоритетов O (1) для моделирования событий с использованием молекулярной динамики" Джеральда Павла. Это позволяет ожидать ожидаемую сложность времени O (K).

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

Ответ 2

РЕДАКТИРОВАТЬ: Это не работает. Я оставляю ответ, потому что, видимо, я не единственный, у кого могла быть такая идея; см. обсуждение ниже. Контрпример: 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, do:

• if 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 -ную большую сумму.

Ответ 3

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

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

Посмотрим: во-первых, массивы отсортированы. Итак, если массивы a и b с длиной M и N, и по мере их размещения наибольшие элементы находятся в слотах M и N соответственно, самая большая пара всегда будет be 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]. Наша самая высокая пара 53+68. Если мы потеряем меньшую из этих двух, наша пара 68+2; если мы потеряем больше, то 53+67. Итак, мы должны смотреть вперед, чтобы решить, какая будет наша следующая пара. Простейшей стратегией обзора является просто вычисление суммы обеих возможных пар. Это всегда будет стоить двух дополнений и двух сравнений для каждого перехода (три, потому что нам нужно иметь дело с случаем, когда суммы равны), позвольте назвать стоимость Q).

Итак, пусть код (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 сравнений на каждой итерации и итерации K-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 украшает каждый элемент своим индексом.

Ответ 4

Если последние два решения были в (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}). Это O (k).

(Нет, нет, все еще не уверен, возможно ли это.)

Ответ 5

Алгоритм max-heap в другом вопросе прост, быстр и правилен. Не стучите. Это действительно хорошо объяснено. fooobar.com/info/291598/...

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