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

Ответ 1

Я нашел ответы по вашей ссылке в основном расплывчатыми и плохо структурированными. Здесь начинаются с алгоритма O (k * log (min (m, n))) O (k * log (m + n)).

Предположим, что они отсортированы по убыванию. Представьте, что вы вычислили матрицу m * n сумм следующим образом:

for i from 0 to m
    for j from 0 to n
        sums[i][j] = a[i] + b[j]

В этой матрице значения монотонно уменьшаются вниз и вправо. Имея это в виду, вот алгоритм, который выполняет поиск по графам через эту матрицу в порядке убывания сумм.

q : priority queue (decreasing) := empty priority queue
add (0, 0) to q with priority a[0] + b[0]
while k > 0:
    k--
    x := pop q
    output x
    (i, j) : tuple of int,int := position of x
    if i < m:
        add (i + 1, j) to q with priority a[i + 1] + b[j]
    if j < n:
        add (i, j + 1) to q with priority a[i] + b[j + 1]

Анализ:

• Цикл выполняется k раз.
  • Для каждой итерации существует одна операция pop.
  • На каждую итерацию может быть до двух операций вставки.
• Максимальный размер очереди приоритетов - O (min (m, n)) O (m + n).
• Очередь приоритетов может быть реализована с помощью двоичной кучи, дающей лог (размер) pop и insert.
• Поэтому этот алгоритм O (k * log (min (m, n))) O (k * log (m + n)).

Обратите внимание, что абстрактный тип абстрактных данных очереди должен быть изменен, чтобы игнорировать повторяющиеся записи. В качестве альтернативы вы могли бы поддерживать отдельную структуру набора, которая сначала проверяет членство в наборе перед добавлением в очередь и удаляет из набора после появления из очереди. Ни одна из этих идей не ухудшит сложность времени и пространства.

Я мог бы написать это на Java, если у вас есть интерес.

Изменить: фиксированная сложность. Существует алгоритм, который имеет описанную мной сложность, но он немного отличается от этого. Вы должны позаботиться о том, чтобы не добавлять определенные узлы. Мое простое решение добавляет много узлов в очередь преждевременно.

Ответ 2

private static class FrontierElem implements Comparable<FrontierElem> {
    int value;
    int aIdx;
    int bIdx;

    public FrontierElem(int value, int aIdx, int bIdx) {
        this.value = value;
        this.aIdx = aIdx;
        this.bIdx = bIdx;
    }

    @Override
    public int compareTo(FrontierElem o) {
        return o.value - value;
    }

}

public static void findMaxSum( int [] a, int [] b, int k ) {
    Integer [] frontierA = new Integer[ a.length ];
    Integer [] frontierB = new Integer[ b.length ];
    PriorityQueue<FrontierElem> q = new PriorityQueue<MaxSum.FrontierElem>();
    frontierA[0] = frontierB[0]=0;
    q.add( new FrontierElem( a[0]+b[0], 0, 0));
    while( k > 0 ) {
        FrontierElem f = q.poll();
        System.out.println( f.value+"    "+q.size() );
        k--;
        frontierA[ f.aIdx ] = frontierB[ f.bIdx ] = null;
        int fRight = f.aIdx+1;
        int fDown = f.bIdx+1;
        if( fRight < a.length && frontierA[ fRight ] == null ) {
            q.add( new FrontierElem( a[fRight]+b[f.bIdx], fRight, f.bIdx));
            frontierA[ fRight ] = f.bIdx;
            frontierB[ f.bIdx ] = fRight;
        }
        if( fDown < b.length && frontierB[ fDown ] == null ) {
            q.add( new FrontierElem( a[f.aIdx]+b[fDown], f.aIdx, fDown));
            frontierA[ f.aIdx ] = fDown;
            frontierB[ fDown ] = f.aIdx;
        }
    }
}

Идея похожа на другое решение, но с учетом того, что по мере добавления к вашему результирующему набору из матрицы на каждом шаге следующий элемент нашего набора может исходить только от того, где текущий набор является вогнутым. Я назвал эти элементы пограничными элементами, и я отслеживаю их положение в двух массивах и их значениях в очереди приоритетов. Это помогает уменьшить размер очереди, но насколько я еще не понял. Кажется, это около sqrt( k ), но я не совсем уверен в этом.

(Конечно, массивы frontierA/B могут быть простыми булевыми массивами, но таким образом они полностью определяют мой результирующий набор. Это не используется нигде в этом примере, но может быть полезно в противном случае.)