Найти пару через 2 массива с k-й наибольшей суммой

Учитывая два отсортированных массива чисел, мы хотим найти пару с k-й по величине возможной суммой. (Пара - это один элемент из первого массива и один элемент из второго массива). Например, с массивами

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

Пары с наибольшими суммами

13 + 16 = 29
13 + 12 = 25
8 + 16 = 24
13 + 8 = 21
8 + 12 = 20

Таким образом, пара с 4-й по величине суммой равна (13,8). Как найти пару с k-й максимально возможной суммой?

Я ищу решение, включающее минимальную кучу или максимальную кучу.

Ответ 1

Это легко сделать в O(k*logk). Я предполагаю, что массивы отсортированы в порядке убывания, чтобы упростить обозначение.

Идея проста. Мы найдем 1-й, 2-й,.., k-й максимальные значения один за другим. Но чтобы даже рассмотреть пару (i, j), нам нужно уже выбрать как (i-1, j), так и (i, j-1), потому что они оба больше или равно (i, j).

Это очень похоже на то, что мы вставляем все пары n*m в кучу, а затем удаляем max k раз. Только нам не нужны все пары n*m.

heap.add(pair(0, 0));  // biggest pair

// remove max k-1 times
for (int i = 0; i < k - 1; ++i) {
    // get max and remove it from the heap
    max = heap.popMax();

    // add next candidates
    heap.add(pair(max.i + 1, max.j));
    heap.add(pair(max.i, max.j + 1));
}

// get k-th maximum element
max = heap.popMax();
maxVal = a[max.i] + b[max.j];

Некоторые вещи, которые следует учитывать.

Дублированные пары могут быть добавлены в кучу, это можно предотвратить с помощью хэша.
Индексы должны быть проверены, например. что max.i + 1 < a.length.

Ответ 2

Я понимаю, что вы хотите кучу, но это не самое эффективное решение, как указывал phimuemue.

Вы можете max_heap оба массива и установить итератор в корне для обоих. На данный момент у вас самая большая сумма.

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

Повторите k раз.

Ответ 3

Вот мой ответ, я думаю, что он хорошо работает, но может ли кто-нибудь сказать мне, в чем его сложность?

Спасибо

int ksum( int a[], int n, int b[], int m, int maxk )
{

    std::vector<int> results;
    int* check = new int[m*n];
    memset( check, 0, n*m*sizeof(int) );

    int finali, finalj;
    int starti = 0, startj = 0;
    for( int k=1; k<maxk+1; ++k )
    {
        int max = 0;
        int maxi=n, maxj=m;
        for( int i=starti; i<n && i<k; ++i )
        {
            if( i>maxj )
                break;
            for( int j=i; j<m && j<k; ++j )
            {
                if( i>maxi && j>=maxj )
                    break;
                if( check[i*m+j] == 0 )
                {
                    int tmp = a[i]+b[j];
                    if( tmp>max )
                    {
                        max = tmp;
                        finali = i, finalj = j;
                    }
                    maxi = i, maxj = j;
                    break;
                }
            }
        }
        starti = finali;

        maxi=n, maxj=m;
        for( int j=startj; j<n && j<k; ++j )
        {
            if( j>maxi )
                break;
            for( int i=j; i<m && i<k; ++i )
            {
                if( j>maxj && i>=maxi )
                    break;
                if( check[i*m+j] == 0 )
                {
                    int tmp = a[i]+b[j];
                    if( tmp>max )
                    {
                        max = tmp;
                        finali = i, finalj = j;
                    }
                    maxi = i, maxj = j;
                    break;
                }
            }
        }
        startj = finalj;

        if( max > 0 )
        {
            check[finali*m+finalj] = 1;
            results.push_back( max );
        }
    }

    delete[] check;
    if( maxk > results.size() )
        return 0;
    else
        return results[maxk-1];
}

int _tmain(int argc, _TCHAR* argv[])
{
    int a[] = {10,8,6,4,1};
    int b[] = {9,6,3,2,1};
    int res = ksum( a, 5, b, 5, 9 );
    return 0;
}