Come trovare il k più grande numero in somme a coppie come setA + setB?

Question

Qui sono impostate due interi, dicono A e B e siamo in grado di ottenere un altro set di C, in cui ogni elemento è la somma di un elemento in A ed elemento b in B.

Ad esempio, A = {1, 2}, B = {3,4} e otteniamo C = {4, 5, 6} dove 4 = 1 + 3, 5 = 1 + 4 = 2 + 3, 6 = 2 + 4

Ora I vuoi scoprire quale numero è il più grande k nell'insieme C, ad esempio 5 è il 2 ° più grande nell'esempio sopra.

Esiste una soluzione efficiente?

So che l'ordinamento delle somme a coppie è un problema aperto e ha un limite inferiore di tempo n^2. Ma dal momento che è necessario solo il maggior numero di k, forse possiamo imparare dall'algoritmo O (n) di trovare il numero mediano in una matrice non ordinata.

Grazie.

Answer 1

Se k è molto vicino a 1 o N, qualsiasi algoritmo che genera pigramente le somme ordinate potrebbe semplicemente essere eseguito fino a quando l'elemento kth o N-kth non viene visualizzato.

In particolare, sto pensando alla ricerca migliore del seguente spazio: (a, b) significa l'oggetto ath da A, il primo elenco, aggiunto al bth da B, il secondo.

Mantieni in una migliore = coppie di code con priorità più bassa (a, b) con costo (a, b) = A [a] + B [b].

Inizia con solo (1,1) nella coda di priorità, che è il minimo.

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) 

Questo vi dà una connettività pettine a denti di sega e si evita di dover marcare ogni (a, b) ha visitato in un array. Nota che costo (a + 1, b)> = costo (a, b) e costo (a, b + 1)> = costo (a, b) perché A e B sono ordinati.

Ecco una foto di un pettine per mostrare la regola di generazione successore sopra (che si avvia in alto a sinistra, una è la direzione orizzontale):

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

E 'solo best-prima esplorazione di (fino a) tutti | A | * | B | tuple e loro somme.

Si noti che la maggior parte delle voci possibili prima dello snapback k è 2 * k, poiché ogni elemento ha 1 o 2 successori. Ecco un possibile stato di coda, in cui gli elementi hanno spinto nella coda sono contrassegnati *:

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

Tutto in alto a sinistra del * frontiera è già stato spuntato.

Per il caso N-k<k, fanno la stessa cosa, ma con ordine coda di priorità inverso e l'ordine di esplorazione (o, semplicemente negare e invertire i valori, ottenere il (N-k) esimo almeno, quindi negare e restituire la risposta).

Vedere anche: elenco ordinato di somme a coppie on SO o Open problems project.

Answer 2

Beh, O (n) sarebbe un limite inferiore (probabilmente non stretto però), altrimenti si potrebbe eseguire l'algoritmo O (n) n volte per ottenere una lista ordinata in O (n^2).

Si può supporre che i due set siano ordinati (li si presenta in ordine sopra)? Se è così, è possibile ottenere qualcosa con un caso medio che è decentemente migliore facendo un "early out", iniziando dall'ultima coppia di elementi, ecc. Solo un sospetto però.

Answer 3

ordinare le matrici A & B: O (mlogm + nlogn) Applicare una forma modificata di un algoritmo per la fusione 2 allineamenti filtrate: O (m + n) cioè ad ogni punto, u somma i due elementi. Quando hai ottenuto (m + n-k + 1) l'elemento in C, interrompi la fusione. Questo elemento è essenzialmente il più grande. E.g. {1,2} & {3,4}: Ordinati C: {1 + 3, (1 + 4) | (2 + 3), 2 + 4}