Jak znaleźć k-tą największą liczbę w sumach par, takich jak setA + setB?

Question

Tutaj są dwie liczby całkowite, powiedzmy A i B i można uzyskać inny zestaw C, w której każdy element jest sumą elementu A w A i B w B. Element

na przykład A = {1 2}, B = {3,4} i otrzymujemy C = {4, 5, 6} gdzie 4 = 1 + 3, 5 = 1 + 4 = 2 + 3, 6 = 2 + 4

Teraz ja chcesz dowiedzieć się, która liczba jest k-tą największą w zestawie C, na przykład 5 jest drugą największą w powyższym przykładzie.

Czy istnieje skuteczne rozwiązanie?

Wiem, że sortowanie kwot parami jest problemem otwartym i ma mniejszy niż 2 czas związany. Ale ponieważ potrzebna jest tylko kt duża liczba, być może możemy się nauczyć z algorytmu O (n) znajdowania medianowej liczby w nieposortowanej tablicy.

Dzięki.

Answer 1

Jeśli k jest bardzo bliskie 1 lub N, każdy algorytm, który leniwie generuje posortowane sumy, może być po prostu uruchomiony, dopóki nie pojawi się element kth lub N-kth.

W szczególności myślę o najlepszym pierwszym wyszukiwaniu w następującej przestrzeni: (a, b) oznacza element ath z A, pierwsza lista dodana do bth z B, druga.

Zachowaj najlepsze pary par o najniższym priorytecie (a, b) z kosztem (a, b) = A [a] + B [b].

Zacznij od just (1,1) w kolejce priorytetów, która jest minimalna.

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) 

To daje łączność grzebień piła-zęba i pozwala uniknąć konieczności oznaczyć każdy (a, b) odwiedził w tablicy. Zauważ, że koszt (a + 1, b)> = koszt (a, b) i koszt (a, b + 1)> = koszt (a, b), ponieważ A i B są posortowane.

Oto zdjęcie z grzebieniem, aby pokazać zasadę następca generacji powyżej (zaczynasz w lewym górnym rogu, a jest kierunek poziomy):

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

To właśnie najlepiej najpierw badanie (do) wszystko | A | * | B | krotki i ich sumy.

Należy pamiętać, że najbardziej możliwe elementy, które zostały przesunięte przed wystrzeleniem k, to 2 * k, ponieważ każdy element ma 1 lub 2 następców. Oto możliwe stan kolejki, w którym elementy wsuwane kolejce są oznaczone *:

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

Wszystko powyżej i na lewo od * granica została już pojawiło.

Dla przypadku zrób to samo, ale z odwróconym porządkiem kolejkowania priorytetów i kolejnością poszukiwań (lub po prostu zaneguj i odwróć wartości, uzyskaj (N-k) co najmniej, a następnie zaneguj i zwróć odpowiedź).

Zobacz także: posortowana lista sum parami on SO lub Open problems project.

Answer 2

Cóż, O (n) byłaby dolną granicą (prawdopodobnie nie jest ciasna), w przeciwnym razie można by uruchomić algorytm O (n) n razy, aby uzyskać posortowaną listę w O (n^2).

Czy możesz założyć, że dwa zestawy są posortowane (prezentujesz je w posortowanej kolejności powyżej)? Jeśli tak, to możesz dostać coś ze średnią skrzynią, która jest zdecydowanie lepsza, wykonując "wczesne wyjście", zaczynając od ostatniej pary elementów itd. Tylko przeczucie.

Answer 3

sortowania tablice & B: O (mlogm + nlogn) Zastosować zmodyfikowaną postać algorytmu łączenia 2 -i tablic: O (m + n) to znaczy w każdym punkcie U sumują się z dwóch elementów. Kiedy już masz (m + n-k + 1) element w C, przestań się scalać. Ten element jest w istocie kogo największy. E.g. {1,2} & {3,4} Posortowane C: {1 + 3, (1 + 4) (2 + 3) 2 + 4}